Word Ladder II

Description

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

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

Notice
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"]
Return
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Link

Lintcode_ladder

Method

1. Record path and depth with bfs, then dfs from end to start to output path
2. Use bfs find the min depth, then dfs with min depth to find the path
3. why we can get the min path ? b/c in the stage of dfs finding the path. we use the "end" as the start. So any path beyonds "end" will be ignored.

Example

1. 1

class Solution {
public:
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return a list of lists of string
      */
    // ----------------------------------------------------------------------
    // Version 1. 
    // bfs : 
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        // write your code here
        vector<vector<string>> result;
        if (dict.empty()) {
            if (start == end) {
                vector<string> tmp = {start, end};
                result.push_back(tmp);
            } else {
                return result;
            }
        }
        dict.insert(start);
        dict.insert(end);
        unordered_map<string, vector<string>> smap;
        unordered_map<string, int> dist;
        // find path
        bfs(start, end, dict, smap, dist);
        vector<string> row;
        // retrive path
        dfs(result, row, end, start, dist, smap);
        return result;
    }
    void dfs(vector<vector<string>>& result, vector<string>& row, string& cur,
            string& start, 
            unordered_map<string, int>& dist,
            unordered_map<string, vector<string>>& smap
    ) {
        row.push_back(cur);
        // reach the start, reverse path then record
        if (cur == start) {
            reverse(row.begin(), row.end());
            result.push_back(row);
            reverse(row.begin(), row.end());
        } else {
            for (auto& next : smap[cur]) {
                if (dist.find(next) != dist.end() 
                    && dist[cur] == dist[next] + 1) { 
                    dfs(result, row, next, start, dist, smap);
                }
            }           
        }
        row.pop_back();
        return;
    }
    // bfs, finding path
    void bfs(string start, string end, unordered_set<string>& dict, 
        unordered_map<string, vector<string>>& smap, 
        unordered_map<string, int>& dist
    ) {
        // unordered_set<string> used;
        queue<string> q;
        int depth = 1;
        int count = 1;
        // bfs
        q.push(start);
        dist[start] = 0;
        while (!q.empty()) {
            string cur = q.front();
            q.pop();
            count--;
            // push cur level
            vector<string> next = getNextString(cur, dict);
            for (auto& s : next) {
                // record path
                smap[s].push_back(cur);
                // de-dup and record depth
                if (dist.find(s) == dist.end()) {
                    dist[s] = dist[cur] + 1;
                    q.push(s);
                }
            }
            // test for next level
            if (count == 0) {
                depth++;
                count = q.size();
            }
        }
        return;
    }
    // find next possible string combination
    vector<string> getNextString(string& s, unordered_set<string>& dict) {
        vector<string> result;
        int len = s.size();
        // get single letter
        for (char ch = 'a'; ch <= 'z'; ++ch) {
            for (int i = 0; i < len; ++i) {
                // get new string with 1 modify
                string cur = s;
                cur[i] = ch;
                // search
                if (dict.find(cur) != dict.end()) {
                   result.push_back(cur); 
                }
            }
        }
        return result;
    }
    // ------------------------------------------------------------------------
    // Version 2. TLE 
    // bfs : find value of min path
    // dfs : find all min path
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        // write your code here
        vector<vector<string>> result;
        if (dict.empty()) {
            if (start == end) {
                vector<string> tmp = {start, end};
                result.push_back(tmp);
            } else {
                return result;
            }
        }
        // // init dict
        dict.insert(start);
        dict.insert(end);
        // bfs : find value of min path
        int minPath = bfs(start, end, dict);
        if (minPath == 0) {
            return result;
        }
        // dfs : find all min path
        vector<string> row;
        row.push_back(start);
        dfs(result, row, 1, minPath, start, end, dict);
        // cout << " depth = " << minPath << endl;
        return result;
    }
    // bfs : find value of min path
    void dfs(vector<vector<string>>& result, vector<string>& row, 
        int path, int minPath, string& start, string& end, unordered_set<string>& dict
    ) {
        if (path > minPath) {
            return;
        }
        if (path == minPath && start == end) {
            result.push_back(row);
            return;
        }
      vector<string> next = getNextString(start, dict);
      int len = next.size();
      for (int i = 0; i < len; ++i) {
        //   if (path + 1 > minPath) {
        //       continue;
        //   }
          row.push_back(next[i]);
          dfs(result, row, path + 1, minPath, next[i], end, dict);
          row.pop_back();
      }
      return;
    }
    // bfs : find all min path
    int bfs(string start, string end, unordered_set<string>& dict) {
        unordered_set<string> used;
        queue<string> q;
        int depth = 1;
        int count = 1;
        // bfs
        q.push(start);
        used.insert(start);
        while (!q.empty()) {
            string cur = q.front();
            q.pop();
            count--;
            // push cur level
            vector<string> next = getNextString(cur, dict);
            for (auto& s : next) {
                // de-dup
                if (used.find(s) != used.end()) {
                    continue;
                }
                // if finding the first match, return depth
                if (s == end) {
                    return depth + 1;
                }
                q.push(s);
                dict.insert(s);
            }
            // test for next level
            if (count == 0) {
                depth++;
                count = q.size();
            }
        }
        return 0;
    }
    // find next possible string combination
    vector<string> getNextString(string& s, unordered_set<string>& dict) {
        vector<string> result;
        int len = s.size();
        // get single letter
        for (char ch = 'a'; ch <= 'z'; ++ch) {
            for (int i = 0; i < len; ++i) {
                // get new string with 1 modify
                string cur = s;
                cur[i] = ch;
                // search
                if (dict.find(cur) != dict.end()) {
                  result.push_back(cur); 
                }
            }
        }
        return result;
    }
};

Similar problems

x

Tags

x