472.Concatenated Words

tags: Hard,Array,String,DP,DFS,Trie

472. Concatenated Words

題目描述

Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

範例

Example 1:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

Example 2:

Input: words = ["cat","dog","catdog"]
Output: ["catdog"]

Constraints:

• 1 <= words.length <= 10⁴
• 1 <= words[i].length <= 30
• words[i] consists of only lowercase English letters.
• All the strings of words are unique.
• 1 <= sum(words[i].length) <= 10⁵

解答

C++

思路

1. 用DP檢查每個單字是否能用除了自己之外的單字來組成

class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        unordered_set<string> s(words.begin(), words.end());
        vector<string> ans;
        for (auto word : words) {
            int n = word.size();
            vector<bool> dp(n + 1, false);
            dp[0] = true;
            for (int i = 0; i < n; i++) {
                if (!dp[i]) continue;
                for (int j = i + 1; j <= n; j++) {
                    if (j - i < n && s.count(word.substr(i, j - i))) {
                        dp[j] = true;
                    }
                }
                if (dp[n]) {
                    ans.push_back(word);
                    break;
                }
            }
        }
        return ans;
    }
};

Yen-Chi ChenMon, Jan 30, 2023

Reference

回到題目列表