472&139 about word concatenation matching

题目

139.

Give you a string and a string array:

s = 'leetcode'
array = ['leet', 'code']

Now, tell me weather string $s$ can be concatenated by words in $array$?

472.

Give you a string array:

array = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatsdogcat"]

Now, tell me which word can be concatenated by other words except itself.

Note: the same words can be used multiple times.

分析

These two question is similar. There are mainly two kind of solutions for both.

1. DP solution

Define a bool array s[...] to be whether the prefix of a word can be concatenated.

For example, for word w, if s[k] is true, it means that w[1...k] can be concatenated by words in the $array$. We split w[1...k] in any positions to find whether there exists one position t, where w[t...k] is in the $array$ and s[t] is true.

So the complexity for this function is $O(n^2)$, ignoring the time of map search.

2. Trie

First, construct the Trie tree using all the words in the array.

Then, DFS the target word. When it come to a leaf node and the target word still has chars, researching the remaining chars from the root.

....