Word Ladder II

Linkage

https://leetcode.com/problems/word-ladder-ii/description/

Idea

The idea of this problem is to combine the BFS(forward) and the DFS(backward) to traverse the visited node. To be more specific, when we are searching the endWord, we should use BFS, which can trim a lot of branch compared to DFS.For reforming the ladder in backward from endWord, we need to maintain a reverse adjacent table, which will record the parent nodes of a child nodes in the BFS process.

TLE Code in Java

public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new LinkedList();
        HashMap<String, Integer> dic = new HashMap();
        HashMap<String, Set<String>> pre = new HashMap();
        List<List<String>> ret = new LinkedList();
        int min_depth = -1;
        for (String word : wordList) {
            dic.put(word, 0);
        }
        dic.put(beginWord, 1);
        
        queue.offer(beginWord);
        
        while(queue.isEmpty() == false) {
            String currentWord = queue.poll();
            
            Integer currentDepth = dic.get(currentWord);
            if (currentDepth == null) currentDepth = 0;
            if (min_depth >= 0 && currentDepth > min_depth) {
                break;   
            }
            for(int position = 0; position < currentWord.length(); position += 1) {
                for (int index = 0; index < 26; index++){
                    char replace = (char) ('a' + index);
                    String newWord = currentWord.substring(0, position) + replace + currentWord.substring(position+1, beginWord.length());
                    if ( newWord.equals(currentWord) ) continue;
                    Integer wordDepth = dic.get(newWord);
        
                    if (wordDepth != null && ( wordDepth == 0 || ( currentDepth < wordDepth ) ) ) {
                        dic.put(newWord,  currentDepth + 1);
                        Set<String> set = pre.get(newWord);
                        if (set == null) {
                            set = new HashSet();
                        }
                        set.add(currentWord);
                        pre.put(newWord, set);
                        
                        if ( newWord.equals(endWord) ) {
                            min_depth = currentDepth;
                        }else {
                            queue.offer(newWord);
                        }
                    }
                }
            }
        }
        
        if(min_depth > 0) {
            List<String> arrayList = new LinkedList<String>();
            arrayList.add(endWord);
            gatherResult(ret, beginWord, endWord, dic, pre, arrayList);
            for (List<String> ret_item : ret) {
                Collections.reverse(ret_item);
            }
        }
        
        return ret;
    }
    
    public void gatherResult(List<List<String>> ret, String startWord, String endWord, HashMap<String, Integer> dic, HashMap<String, Set<String>> pre, List<String> ret_item){
        if (endWord.equals(startWord)) {
            ret.add(ret_item);
            return;
        }
        Set<String> nextWordList = pre.get(endWord);
        for (String word : nextWordList) {
            List<String> new_item = new LinkedList(ret_item);
            new_item.add(word);
            gatherResult( ret, startWord, word, dic, pre, new_item);
        }
    }
}

Accept Code In C++

class Solution {
public:
    vector<vector<string> > findLadders(string beginWord, string endWord, vector<string> &wordList) {
        vector<std::vector<string> > ret;
        queue<string> node_queue;
        unordered_map<string, int> word_dic;
        unordered_map<string, unordered_set<string> > reverse_adjacent_table;
        int min_depth = -1;


        for (vector<string>::iterator iter = wordList.begin(); iter != wordList.end(); iter++) {
            word_dic[*iter] = 0;
        }
        word_dic[beginWord] = 1;

        node_queue.push(beginWord);

        while (node_queue.empty() == false) {
            string currentWord = node_queue.front();
            node_queue.pop();
            int currentDepth = word_dic.find(currentWord)->second;
            if (min_depth >= 0 && currentDepth > min_depth) break;

            for (int position = 0; position < currentWord.size(); position++) {

                string newWord = currentWord;
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    newWord[position] = ch;
                    if (newWord == currentWord) continue;
                    auto iter = word_dic.find(newWord);
                    if (iter == word_dic.end()) continue;
                    int wordDepth = iter->second;
                    if (wordDepth == 0 || currentDepth < wordDepth) {
                        word_dic[newWord] = currentDepth + 1;
                        auto iter = reverse_adjacent_table.find(newWord);
                        unordered_set<string> *set;
                        if (iter == reverse_adjacent_table.end()) {
                            set = new unordered_set<string>();
                        } else {
                            set = &iter->second;
                        }
                        set->insert(currentWord);
                        pair<string, unordered_set<string> > string2set(newWord, *set);
                        reverse_adjacent_table[newWord] = *set;

                        if (newWord == endWord) {
                            min_depth = currentDepth;
                        } else {
                            node_queue.push(newWord);
                        }
                    }
                }
            }
        }

        vector<string> ret_item;
        if (min_depth > 0) {
            ret_item.push_back(endWord);
            this->gatherResult(beginWord, endWord, ret, ret_item, reverse_adjacent_table);
        }

        for(auto iter = ret.begin(); iter != ret.end(); iter++) {
            reverse(iter->begin(), iter->end());
        }

        return ret;
    }

    void gatherResult(const string &startWord, const string &endWord, vector<std::vector<string> >& ret, vector<string>& ret_item, unordered_map<string, unordered_set<string> >& reverse_adjacent_table) {
        if (endWord == startWord) {
            ret.push_back(ret_item);
            return;
        }

        unordered_set<string> nextWordList = reverse_adjacent_table[endWord];

        for (unordered_set<string>::iterator iter = nextWordList.begin(); iter != nextWordList.end(); iter++) {
            vector<string> *new_item = new vector<string>(ret_item);
            new_item->push_back(*iter);
            gatherResult(startWord, *iter, ret, *new_item, reverse_adjacent_table);
        }
    }

};