My C++ Solution based on Previous Problem 'Word Break'


  • 0
    G

    This problem is pretty much similar to the previous one Word Break.
    Firstly, we need to sort the array via the length of word, which means we put the short one ahead.
    Secondly, we create a dictionary that put all the words in it. For each word, we run the Word Break method to see whether it can be broken into other words. Remember, the dictionary should erase current word, and then insert back after the check.

    class Solution {
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            if (words.size() <= 1) return {};
            vector<string> res;
            unordered_set<string> dict;
            sort(words.begin(), words.end(), [](string& a, string& b){return a.size() < b.size();});
            for (string word : words) dict.insert(word);
            for (int k = 1; k < words.size(); ++k) {
                dict.erase(words[k]);
                int len = words[k].size();
                vector<bool> v(len + 1, false);
                v[0] = true;
                for (int i = 0; i < len + 1; ++i) {
                    for (int j = 0; j < i; ++j) {
                        if (v[j] && dict.count(words[k].substr(j, i - j))) {
                            v[i] = true;
                            break;
                        }
                    }
                }
                if (v.back()) res.push_back(words[k]);
                dict.insert(words[k]);
            }
            return res;
        }
    };

Log in to reply
 

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