Word Ladder

• Lintcode : 120 / Leetcode : 127
• Level : Hard

Problem

Given two words (start and end), and a dictionary, find the shortest transformation sequence from start to end, output the length of the sequence.
Transformation rule such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary. (Start and end words do not need to appear in the dictionary )
Example
Example 1:

Input：start = "a"，end = "c"，dict =["a","b","c"]
Output：2
Explanation：
"a"->"c"
Example 2:

Input：start ="hit"，end = "cog"，dict =["hot","dot","dog","lot","log"]
Output：5
Explanation：
"hit"->"hot"->"dot"->"dog"->"cog"
Notice
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n avg(wordlen) 26)
space: O(n)

Answer

class Solution {
public:
    int ladderLength(string &start, string &end, unordered_set<string> &dict) {
        // corner case 

        queue<string> q;
        dict.insert(end);
        map<string, int> map;
        int step = 1;
        map[start] = step;
        q.push(start);
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                string s = q.front(); q.pop();
                if (s == end) return map[end];
                int len = s.size();
                for (int i = 0; i < len; i++) {
                    char c = s[i];
                    for (char cha = 'a'; cha <= 'z'; cha++) {
                        s[i] = cha;
                        if (cha == c || dict.find(s) == dict.end()) continue;
                        // 不走回頭路
                        if (map[s] == 0) {
                            map[s] = step + 1;
                            q.push(s);
                        }
                    }
                    s[i] = c;
                }
            }
            step++;
        }
        return -1;
    }
};

tags: BFS

​