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