Leetcode.127.Word Ladder

题目

给定一个字符串数组, 所有字符串长度都一样, 没有重复字符串. 给一个beginString和一个endString.通过beginString每次变换一个字符, 找到endString. 字符串数组的顺序可以打乱, 输出最小连接长度.

Input: {"hot","dot","dog","lot","log","cog"}, "hit", "cog"
Output:  5
Input: {"a","b","c"}, "a", "c"
Output: 2
Input: {"hot","dot","dog","lot","log"}, "hit", "cog"
Output: 0
Input: {"ts","sc","ph","ca","jr","hf","to","if","ha","is","io","cf","ta"}, "ta", "if"
Output: 4

思路1

FBS. 时间复杂度过多, 需要过滤部分字符.

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    vector<string> vec;
    vector<string> words;

    queue<string> q;
    unordered_set<string> s;
    q.push(beginWord);
    s.insert(beginWord);

    int level = 0;
    while(!q.empty()) {
        level++;
        int size = (int)q.size();
        for (int i = 0; i < size; i++) {
            string str = q.front();
            q.pop();
            if (str == endWord) {
                return level;
            }
            for(int i = 0;i< wordList.size();i++) {
                if (isMatchLadder(wordList[i], str) &&
                    find(s.begin(), s.end(), wordList[i]) == s.end()) {
                    s.insert(wordList[i]);
                    q.push(wordList[i]);
                }
            }
        }
    }

    return 0;
}

思路2

过滤字符.

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> words(wordList.begin(),wordList.end());
    unordered_set<string> s;
    unordered_map<string,int> level;
    queue<string> q;
    q.push(beginWord);
    s.insert(beginWord);
    level[beginWord]=1;

    while(!q.empty()){
        string str = q.front();
        q.pop();

        if(str == endWord){
            return level[str];
        }
        for(int i = 0;i < str.size(); i++) {
            for(char c ='a'; c <= 'z'; c++) {
                if(c == str[i]) continue;
                string tmp = str;
                tmp[i] = c;
                if(words.count(tmp) && !s.count(tmp)){
                    q.push(tmp);
                    s.insert(tmp);
                    level[tmp] = level[str] + 1;
                }
            }
        }
    }

    return 0;
}

总结

熟练掌握BFS和DFS的循环和递归方法.