Word Ladder II [leetcode]

Word Ladder II [leetcode]

本題有幾個注意點：

1. 回溯找路徑時，根據路徑的最大長度控制回溯深度

2. BFS時，在找到end單詞後，給當前層做標記find=true，遍歷完當前層後結束。不需要遍歷下一層了。

3. 可以將字典中的單詞刪除，替代visited的set，這樣優化以後時間從1700ms+降到800ms+

代碼如下：

class Solution {
public:
    vector> findLadders(string start, string end, unordered_set &dict) {
        set queue[2];
        queue[0].insert(start);
        vector> res;
        bool find = false;
        int length = 1;
        bool cur = false;
        map> mapping;
        
        //bfs
        while (queue[cur].size() && !find)
        {
            length++;
            for (set::iterator i = queue[cur].begin(); i != queue[cur].end(); i++)//delete from dictionary
                dict.erase(*i);
            for (set::iterator i = queue[cur].begin(); i != queue[cur].end(); i++)
            {
                for (int l = 0; l < (*i).size(); l++)
                {
                    string word = *i;
                    for (char c = 'a'; c <= 'z'; c++)
                    {
                        word[l] = c;
                        if (dict.find(word) != dict.end())
                        {
                            if (mapping.find(word) == mapping.end()) mapping[word] = set();
                            mapping[word].insert(*i);
                            if (word == end) find = true;
                            else             queue[!cur].insert(word);
                        }
                    }
                }
            }
            queue[cur].clear();
            cur = !cur;
        }
        if (find)
        {
            vector temp;
            temp.push_back(end);
            getRes(mapping, res, temp, start, length);
        }
        
        return res;
    }
    
    void getRes(map> & mapping, vector> & res, vector temp, string start, int length)
    {
        if (temp[0] == start)
        {
            res.push_back(temp);
            return;
        }
        if (length == 1) return;//recursion depth
        string word = temp[0];
        temp.insert(temp.begin(), "");
        for (set::iterator j = mapping[word].begin(); j != mapping[word].end(); j++)
        {
            temp[0] = *j;
            getRes(mapping, res, temp, start, length - 1);
        }
    }
};