主題
題目連結：
題目意譯：
給定一個字串陣列 words（無重複字詞），回傳這個給定的字詞串列中所有的串接詞。
一個串接詞定義為一個由給定陣列中至少兩個較短字詞（可重複選擇）所組成之字串。
限制：
1 ≦ words.length ≦ 10 ^ 4
1 ≦ words[i].length ≦ 30
words[i] 只由小寫英文字母組成。
words 中所有字串彼此相異。
1 ≦ sum(words[i].length) ≦ 10 ^ 5
範例測資：
範例 1：
輸入： words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
輸出： ["catsdogcats","dogcatsdog","ratcatdogcat"]
解釋： "catsdogcats" 可由 "cats" 、 "dog" 和 "cats" 串接而成。
"dogcatsdog" 可由 "dog" 、 "cats" 和 "dog" 串接而成。
"ratcatdogcat" 可由 "rat" 、 "cat" 、 "dog" 和 "cat" 串接而成。
範例 2：
輸入： words = ["cat","dog","catdog"]
輸出： ["catdog"]
解題思維：
首先先把 words 中所有字詞中丟進一個雜湊表（Hash Table）中，方便判斷一個字串是否存在於 words 中。
接著檢查 words 中每一個字詞各自可不可以被拆成若干個 words 中的字詞。而這可以利用動態規劃（Dynamic Programming，DP）來判斷，方式類似於這題：
（令目前要判斷的字詞為 S）
定義一個陣列 D，其中 D[i] 代表 S 前 i 個字母所形成的子字串（可表為 S[0 …… i - 1]）是否可以拆解成 words 中的字詞來組成的。若 D[i] = true，代表可以；反之若 D[i] = false，則代表不行。
遞迴式如下：
D[0] = true、
D[i] = DP[j1] || DP[j2] || ……，其中 i > 0 、 j1 、 j2 、…… < i 且 s[j1 …… i - 1] 、 s[j2 …… i - 1] 、…… 為 words 中的字詞（此可用先前提及的雜湊表判斷）。
（其中「||」為邏輯或）
而最後所求即為 DP[S.size()]。
如果 DP[S.size()] 代表著 S 可以被拆解成 words 中的字詞，則將 S 加到結果陣列中。
最後回傳結果陣列即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
