Posted on 2023-01-27 17:29
Uriel 阅读(29)
评论(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