Word Concatenation

Description

Given a list of unique strings words, return the number of words that are concatenations of other words in the list. You can reuse words when concatenating and concatenate any number of times.

Constraints:

• n ≤ 100,000 where n is the length of words
• m ≤ 100 where m is the max length of a string in words

Example 1

Input

words = ["news", "paper", "newspaper", "binary", "search", "binarysearch"]

Output

2

Explanation

"newspaper" is concatenation of "news" and "paper". "binarysearch" is concatenation of "binary" and "search".

---

Example 2

Input

words = ["cc", "c"]

Output

1

Explanation

"cc" is a concatenation of "c" and "c".

---

Intuition

1. create a dictionary
2. look up substring in this dictionary

Implementation

import java.util.*;

class Solution {
    private final Set<String> DICTIONARY = new HashSet<>();
    public int solve(String[] words) {
        Collections.addAll(DICTIONARY, words);
        int ans = 0;
        for (String word : words) {
            if (isConcatenation(word, 0)) {
                ans++;
            }
        }
        return ans;
    }

    private boolean isConcatenation(String wordStr, int wordCount) {
        int n = wordStr.length();
        if (n == 0) {
            return wordCount > 1;
        }
        for (int i = 1; i <= n; i++) {
            String prefix = wordStr.substring(0, i);
            if (DICTIONARY.contains(prefix)
                && isConcatenation(wordStr.substring(i), wordCount + 1)) {
                return true;
            }
        }
        return false;
    }
}

Time Complexity

• Time: O(n^2)
• Space: O(n)