Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给定一堆单词组成的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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理