C++ 772 ms dp solution

  • 8

    For any qualified word, there must be at least 3 indexes (at least 1 besides 0 and n-1 which n is the length of the word), which can be used to split the whole string to at least two sub strings and all sub strings can be found in words.
    E.g. input ["cat","cats", "dog", "sdog","dogcatsdog"], for word dogcatsdog, there are 2 sets of numbers: [0, 3, 6, 10] and [0, 3, 7, 10] which can be formed by concatenating [dog, cat, sdog] and [dog, cats, dog] respectively.
    So, we can use a vector<int> dp(n+1) to store if w.substr(0, i) can be formed by existing words. Once i reach to n and it is not the word itself, we put the word to results.

        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            unordered_set<string> s(words.begin(), words.end());
            vector<string> res;
            for (auto w : words) {
                int n = w.size();
                vector<int> dp(n+1);
                dp[0] = 1;
                for (int i = 0; i < n; i++) {
                    if (dp[i] == 0) continue;
                    for (int j = i+1; j <= n; j++) {
                        if (j - i < n && s.count(w.substr(i, j-i))) dp[j] = 1;
                    if (dp[n]) { res.push_back(w); break; }
            return res;

  • 0

    @Hcisly this is a O(n^3) solution u can make it O(n^2) by doing rabin karp hash on string ,anyhow this is not the inteneded solution , intended solution shud be O(n)or O(nlogn)

Log in to reply

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