Posted on 2023-01-27 17:29
Uriel 閱讀(48)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
字符串處理 、
閑來無事重切Leet Code
給定一堆單詞組成的list，輸出其中可以由至少兩個list中其他單詞組成的所有單詞（可以重復使用單詞）
DP，對于每一個單詞w，開一個DP list，list長度為w的長度+1，dp[0]=1，之后若直到w的第i位可以用單詞表中的其他單詞組成，則dp[i]=1，若dp[len(w)]=1，則輸出該單詞
先將list轉為set，加速后續查找單詞的速度
復雜度O(n*L*L)，運行效率好像一般
1 #472
2 #Runtime: 1236 ms (Beats 20%)
3 #Memory: 16.6 MB (Beats 88.57%)
4
5 class Solution(object):
6 def findAllConcatenatedWordsInADict(self, words):
7 """
8 :type words: List[str]
9 :rtype: List[str]
10 """
11 word_dict = set(words)
12 ans = []
13 for w in words:
14 dp = [0] * (len(w) + 1)
15 dp[0] = 1
16 for i in range(len(w)):
17 if not dp[i]:
18 continue
19 for j in range(i + 1, len(w) + 1):
20 if j - i < len(w) and w[i:j] in word_dict:
21 dp[j] = 1
22 if dp[len(w)]:
23 ans.append(w)
24 break
25 return ans