C++ DFS Easy to Understand Solution


  • 0
    S
    class Solution {
    public:
    
        bool dfs(string& word, int minLen, unordered_map<int, unordered_set<string>>& dict) {
            int N = word.length();
            for (int i = minLen; i + minLen <= N; ++i) {
                string prefix = word.substr(0, i);
                string suffix = word.substr(i);
                if (dict.find(i) != dict.end() && dict[i].find(prefix) != dict[i].end()) {
                    if(dict.find(N-i) != dict.end() && dict[N-i].find(suffix) != dict[N-i].end()) {
                        return true;
                    } else {
                        if(dfs(suffix, minLen, dict)) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            vector<string> res;
            if(words.empty()) return res;
            unordered_map<int, unordered_set<string>> dict;
            int minLen = INT_MAX;
            for (auto word : words) {
                dict[word.size()].insert(word);
                minLen = min(minLen, (int)word.size());
            }
            dict.erase(0);
            if(dict.empty()) return res;
            for (auto word : words) {
                if(dfs(word, minLen, dict)) {
                    res.push_back(word);
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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