Word Ladder

Description

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

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

Notice
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

Example
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Link

Lintcode_ladder

Method

1. bfs to find middle result, then use the O(keyLen*26) to find next possible middle result
2. x

Example

1. 1

class Solution {
public:
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return an integer
      */
    // Version 1. use "depth" and "count" to proc level 
    int ladderLength(string start, string end, unordered_set<string>& dict) {
        if (dict.empty()) {
            return 0;
        }
        if (start == end) {
            return 1;
        }
        // init
        dict.insert(end);
        queue<string> q;
        unordered_set<string> used;
        // Bfs Version 1
        int depth = 1;
        int count = 1;
        q.push(start);
        used.insert(start);
        while (!q.empty()) {
            string cur = q.front();
            q.pop();
            count--;
            vector<string> nextstring = helper(cur, dict);
            for (auto& i : nextstring) {
                // cannot go back to prev string
                if (used.find(i) != used.end()) {
                    continue;
                }
                // find the target path
                if (i == end) {
                    return depth + 1;
                }
                q.push(i);
                used.insert(i);
            }
            // if current level finished, redo count/deep for next level
            if (count == 0) {
                depth++;
                count = q.size();
            }
        }
        return 0;
    }
    // -------------------------------------------------------------------------
    // Version 2. bfs with one by one level process 
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // write your code here
        // exception
        if (dict.empty()) {
            return 0;
        }
        if (start == end) {
            return 1;
        }
        // init
        // We have to insert end, while start is not needed 
        // So in the matching part, we has chance to return target end
        // dict.insert(start);
        dict.insert(end); 
        queue<string> q;
        unordered_set<string> used;
        // Bfs version 2
        int step = 1;
        q.push(start);
        used.insert(start);
        while (!q.empty()) {
            // update depth to current level
            step++;
            // process the current whole level
            int qlen = q.size();
            for (int i = 0; i < qlen; ++i) {
                string cur = q.front();
                q.pop();
                vector<string> nextstring = helper(cur, dict);
                for (auto& i : nextstring) {
                    // cannot go back to prev string
                    if (used.find(i) != used.end()) {
                        continue;
                    }
                    // find the target path
                    if (i == end) {
                        return step;
                    }
                    q.push(i);
                    used.insert(i);
                }
            }
        }
        return 0;
    }
    // ---------------------------------------------------------------------
private:
    // Searching intermidate "s" from "dict", with modifying only one letter
    // O(26 * s.size() * s.size())
    vector<string> helper(string& s, unordered_set<string>& dict) {
        vector<string> result;
        string cur;
        for (char ch = 'a'; ch <= 'z'; ++ch) {
            for (int j = 0; j < s.size(); ++j) {
                // replace ch with j index
                cur = s;
                cur[j] = ch;
                // test the dict has it
                if (dict.find(cur) == dict.end()) {
                    continue;
                }
                // record candidates
                result.push_back(cur);
            }
        }
        return result;
    }
};

Similar problems

x

Tags

x