单词接龙

给出两个单词（start和end）和一个字典，找到从start到end的最短转换序列

比如：

1. 每次只能改变一个字母。
2. 变换过程中的中间单词必须在字典中出现。

样例

给出数据如下：

start = "hit"

end = "cog"

dict = ["hot","dot","dog","lot","log"]

一个最短的变换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，

返回它的长度 5

 

思路：这时一道bfs的题，开始突然反应不过来。 可以想象成一棵树，根节点是start字符串，第二层是所有的和它相差一个字母的字符串（之前出现过的，之后就没有必要出现了，因为出现的话，也是abc变成bbc又变回abs，没有意义），用一个hashmap来保存每一个节点的所处的层数，还需要一个队列来实现广度优先搜索，因为是从顶层到底层来遍历的，所以发现等于end的时候的层数值就是最小的，返回即可。

java版本的（超时，没通过）

 

public class Solution {
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return an integer
      */
    public int ladderLength(String start, String end, Set<String> dict) {
        // write your code here
        if(start==null||end==null||dict.size()==0){
            return 0;
        }
        if(start==end){
            return 2;
        }
        if(start.length()!=end.length()){
            return 0;
        }
        Queue<String> que=new LinkedList<String>();
        HashMap<String,Integer> map=new HashMap<String,Integer>();
        que.add(start);
        map.put(start,1);
        while(!que.isEmpty()&&!dict.isEmpty()){
            String temp=que.remove();
            int n=map.get(temp);
            for(String i:dict){
                if(isnext(temp,i)){
                    que.add(i);
                    dict.remove(i);
                    map.put(i,n+1);
                    if(i==end){
                        return map.get(i);
                    }
                }
            
            }
        }
        return 0;
    }
    public boolean isnext(String s1,String s2){
        if(s1.length()!=s2.length()){
            return false;
        }
        char[] arr1=s1.toCharArray();
        char[] arr2=s2.toCharArray();
        for(int j=0;j<arr1.length;j++){
            for(char i='a';i<='z';i++){
                arr1[j]=i;
                if(issame(arr1,arr2)){
                    return true;
                }
            }
        }
        return false;

    }
    public boolean issame(char[] arr1,char[] arr2){
        for(int i=0;i<arr1.length;i++){
            if(arr1[i]!=arr2[i]){
                return false;
            }
        }
        return true;
    }
}

 

 

 

c版本的

 

class Solution {
public:
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return an integer
      */
    int ladderLength(string start, string end, unordered_set<string> &dict) {    

        vector<vector<string>> result;
        if(start.size() == 0 || end.size() == 0 || dict.size() == 0) {
            return 0;
        }

        //start 和 end 都为‘a’, dict 为‘b’ 答案是1？？？？？
        if(start.size() == end.size() && start.size() == 1) {
            return 1;
        }

        map<string, int> count; //到某个字符串时，序列的长度
        queue<string> qu;
        qu.push(start);
        dict.erase(start);
        count[start] = 1;

        int minLen = 0x7fffffff;
        vector<string> curList;

        while(!qu.empty() && dict.size() >= 0) {
            string curString = qu.front();
            qu.pop();
            int curLen = count[curString];
            for(int i = 0; i < curString.size(); ++i) {
                string tmp = curString;
                for(char j = 'a'; j <= 'z'; ++j) {
                    if(tmp[i] == j) {
                        continue;
                    } else {
                        tmp[i] = j;

                        if(dict.find(tmp) != dict.end()) {
                            //cout << tmp << endl;
                            qu.push(tmp);
                            count[tmp] = curLen + 1;
                            dict.erase(tmp);
                            if(tmp == end) {
                                return count[tmp]; //end可能包含在dict中
                            }
                        } else if(tmp == end) {
                            //cout << tmp << endl;
                            count[tmp] = count[curString] + 1;
                            return count[tmp];
                        }
                    }
                }
            }
        } 

        return 0;
    } 
};