0472. Concatenated Words

https://leetcode.com/problems/concatenated-words

Description

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

• 0 <= words[i].length <= 1000

• words[i] consists of only lowercase English letters.

• 0 <= sum(words[i].length) <= 105

ac1: dp

similar to #139 work break. careful about "at least 2 words"

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> res = new ArrayList<>();
        // edge cases
        if (words == null || words.length < 2) return res;

        Set<String> set = new HashSet<>();
        for (String s : words) set.add(s);

        for (String s : words) {
            if (wordbreak(set, s)) 
                res.add(s);
        }

        return res;
    }

    private boolean wordbreak(Set<String> set, String s) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        int cnt = 0;  // comprise of at least 2 words
        for (int i = 1; i < dp.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    cnt++;
                    if (j == 0 && i == s.length()) cnt = 1;  // only single word
                    break;
                }
            }
        }
        return dp[dp.length-1] && cnt > 1;
    }
}

ac2: trie

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> res = new ArrayList<>();
        // edge cases
        if (words == null || words.length < 2) return res;

        TrieNode root = new TrieNode();
        for (String s : words) {
            if (s.length() == 0) continue; // edge case
            add(root, s);
        }

        for (String s : words) {
            if (validate(root, s, 0)) res.add(s);
        }

        return res;
    }
    private boolean validate(TrieNode root, String s, int start) {
        TrieNode r = root;
        for (int i = start; i < s.length(); i++) {
            int pos = s.charAt(i) - 'a';
            if (r.next[pos] == null) return false;
            r = r.next[pos];
            if (r.isWord) {
                if (validate(root, s, i+1)) return true;
            }
        }
        return r.isWord && start != 0;
    }
    private void add(TrieNode root, String s) {
        TrieNode r = root;
        for (int i = 0; i < s.length(); i++) {
            int pos = s.charAt(i) - 'a';
            if (r.next[pos] == null) r.next[pos] = new TrieNode();
            r = r.next[pos];
        }
        r.isWord = true;
    }
}

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    boolean isWord = false;
}

/*
Time complexity:
1) Build trie: O(nk), n for words.size(), k for avg length of words.
2) Validate: O(nk).
Space: Trie worst case n*k, where no word share same branch in trie.
*/