LeetCode: Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

---

We can still use BFS to find the shortest path for this problem. What we need to do additionally is record the path when we do BFS. Here we can use a map to record the list of words that can transform to one word in the dict. Then we can use backtracking to generate the path.

C++ Code:

/*
 * func: generate_path
 * goal: generate shortest parth from the the map
 * @param prev_map: a word map to show the words connected to
 * @param path: a path vector
 * @param word: current word
 * @param result: final result set
 * return:
 */
void generate_path(unordered_map<string, vector<string> > &prev_map, vector<string> &path,
                   string word, vector<vector<string> > &result){
    if(prev_map[word].size() == 0){
        path.emplace_back(word);
        vector<string> curr_path = path;
        reverse(curr_path.begin(), curr_path.end());
        result.emplace_back(curr_path);
        path.pop_back();
        return;
    }
    
    path.push_back(word);
    for(auto iter = prev_map[word].begin(); iter != prev_map[word].end(); ++iter){
        generate_path(prev_map, path, *iter);
    }
    path.pop_back();
}

/*
 * func: find_ladders
 * goal: find all shortest transformation sequences
 * @param start: start string
 * @param end: end string
 * @param dict: words dict
 * return: all possible sequences
 */
vector<vector<string> > find_ladders(string start, string end, unordered_set<string> &dict){
    vector<vector<string> > result;
    
    unordered_map<string, vector<string> > prev_map;
    for(auto it = dict.begin(); it != dict.end(); ++it){
        prev_map[*it] = vector<string>();
    }
    
    vector<unordered_set<string> > candidates(2);
    int current = 0;
    int previous = 1;
    candidates[current].insert(start);
    
    while(true){
        current = !current;
        previous = !previous;
        
        for(auto it = candidates[previous].begin(); it != candidates[previous].end(); ++it){
            dict.erase(*it);
        }
        
        candidates[current].clear();
        for(auto it = candidates[previous].begin(); it != candidates[previous].end(); ++it){
            for(size_t pos = 0; pos < it->size(); ++pos){
                string word = *it;
                for(char c = 'a'; c <= 'z'; ++c){
                    word[pos] = c;
                    if(dict.count(word) > 0){
                        prev_map[word].push_back(*it);
                        candidates[current].insert(word);
                    }
                }
            }
        }
        
        if(candidates[current].size() == 0){
            return result;
        }
        if(candidates[current].count(end)){
            break;
        }
    }
    
    vector<string> path;
    generate_path(prev_map, path, end, result);
    
    return result;
}

Python Code:

# func: find all shortest transformation sequences
# @param start: start string
# @param end: end string
# @param dict: words dict
# @return: all sequences
def find_ladders(start, end, dict):
    dict.add(end)
    dict.add(start)
    result = []
    path = []
    #a map store current word as key and words can connected to it as value
    prev_map = {word:[] for word in dict}
    #two sets help BFS
    current = set()
    previous = set()
    current.add(start)
    while end not in current:
        current, previous = previous, current
        for word in previous:
            dict.remove(word)

        current.clear()
        for word in previous:
            for i in xrange(len(word)):
                for ch in 'abcdefghijklmnopqrstuvwxyz':
                    transformed = word[:i] + ch + word[i+1:]
                    if transformed in dict:
                        prev_map[transformed].append(word)
                        current.add(transformed)

        if not current:
            return []
    #Generate path based on the prev_map
    #It is a backtracking
    def generate_path(word):
        if len(prev_map[word]) == 0:
            path.append(word)
            result.append(path[::-1])
            path.pop(-1)
            return

        path.append(word)
        for prev_word in prev_map[word]:
            generate_path(prev_word)

        path.pop(-1)

    generate_path(end)
    return result