DEV Community

Cover image for 472. Concatenated Words
Harsh Rajpal
Harsh Rajpal

Posted on

472. Concatenated Words

Problem Statement:

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 <= 104
  • 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) <= 105

Solution:

Code:

class Solution {
  public List<String> findAllConcatenatedWordsInADict(String[] words) {
    List<String> ans = new ArrayList<>();
    Set<String> wordSet = new HashSet<>(Arrays.asList(words));
    Map<String, Boolean> memo = new HashMap<>();

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

    return ans;
  }

  private boolean wordBreak(final String word, Set<String> wordSet, Map<String, Boolean> memo) {
    if (memo.containsKey(word))
      return memo.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, memo))) {
        memo.put(word, true);
        return true;
      }
    }

    memo.put(word, false);
    return false;
  }
}
Enter fullscreen mode Exit fullscreen mode

Sentry image

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here →

Top comments (0)

Heroku

This site is powered by Heroku

Heroku was created by developers, for developers. Get started today and find out why Heroku has been the platform of choice for brands like DEV for over a decade.

Sign Up

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay