Are all test cases satisfy this condition: start and end belong to dict?


  • 0
    U

    My question is in the title:
    Are all test cases satisfy this condition: start and end belong to dict?

    For example:

    Type A : All test cases are like :
    Start="hot", End="dog", Dict=["hot","dog","dot"]

    But not like this:
    Type B:
    Start = "hit",End = "cog",Dict = ["hot","dot","dog","lot","log"]

    Because I use DFS to flag the parent node. If I note "//...!!!", the code AC. But this code is for Type A.
    If I do not note "//...!!!", the code WA.

    class Solution {
    private:
        unordered_map<string, vector<string>> father;
        vector<vector<string>> res;
        
        void dfs(vector<string> &path, string &start, string &end) {
            path.push_back(end);
            if(start == end) {
                res.push_back(path);
                reverse(res.back().begin(), res.back().end());
                path.pop_back();
                return;
            }
            vector<string> pre_words = father.find(end)->second;
            for(int i = 0; i < pre_words.size(); ++i) {
                dfs(path, start, pre_words[i]);
            }
            path.pop_back();
        }
    public:
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
            if(start == end) return res;
            bool found = false;
            unordered_set<string> current_visit, next;
            unordered_set<string> flag;
            current_visit.insert(start);
            while(!current_visit.empty() && !found) {
                for(const auto word : current_visit) {
                    flag.insert(word);
                }
                for(auto word : current_visit) {
                    for(int i = 0; i < word.size(); ++i) {
                        for(char c = 'a'; c <= 'z'; ++c) {
                            if(word[i] == c) continue;
                            string tmp = word;
                            tmp[i] = c;
                            if(tmp == end) {
                                found = true;
                                //father[tmp].push_back(word); !!!
                            }
                            if(dict.find(tmp) != dict.end() && flag.find(tmp) == flag.end()) {
                                next.insert(tmp);
                                father[tmp].push_back(word);
                            }
                        }
                    }
                }
                current_visit.clear();
                swap(current_visit, next);
            }
            if(found) {
                vector<string> path;
                dfs(path, start, end);
            }
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.