Skip to content

472. Concatenated Words 👍

  • Time: $O(n\ell^3)$, where $n = |\texttt{words}|$ and $\ell = \max(|\texttt{words[i]}|)$
  • Space: $O(n\ell)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
    vector<string> ans;
    unordered_set<string> wordSet{words.begin(), words.end()};
    unordered_map<string, bool> mem;

    for (const string& word : words)
      if (isConcat(word, wordSet, mem))
        ans.push_back(word);

    return ans;
  }

 private:
  bool isConcat(const string& s, const unordered_set<string>& wordSet,
                unordered_map<string, bool>& mem) {
    if (const auto it = mem.find(s); it != mem.cend())
      return it->second;

    for (int i = 1; i < s.length(); ++i) {
      const string prefix = s.substr(0, i);
      const string suffix = s.substr(i);
      if (wordSet.count(prefix) &&
          (wordSet.count(suffix) || isConcat(suffix, wordSet, mem)))
        return mem[s] = true;
    }

    return mem[s] = false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public List<String> findAllConcatenatedWordsInADict(String[] words) {
    List<String> ans = new ArrayList<>();
    Set<String> wordSet = new HashSet<>(Arrays.asList(words));
    Map<String, Boolean> mem = new HashMap<>();

    for (final String word : words)
      if (wordBreak(word, wordSet, mem))
        ans.add(word);

    return ans;
  }

  private boolean wordBreak(final String word, Set<String> wordSet, Map<String, Boolean> mem) {
    if (mem.containsKey(word))
      return mem.get(word);

    for (int i = 1; i < word.length(); ++i) {
      final String prefix = word.substring(0, i);
      final String suffix = word.substring(i);
      if (wordSet.contains(prefix) &&
          (wordSet.contains(suffix) || wordBreak(suffix, wordSet, mem))) {
        mem.put(word, true);
        return true;
      }
    }

    mem.put(word, false);
    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
    wordSet = set(words)

    @functools.lru_cache(None)
    def isConcat(word: str) -> bool:
      for i in range(1, len(word)):
        prefix = word[:i]
        suffix = word[i:]
        if prefix in wordSet and (suffix in wordSet or isConcat(suffix)):
          return True

      return False

    return [word for word in words if isConcat(word)]