(接頭辞ツリー)leetcode 1365.現在の数字より小さい数字はどれくらいありますか472.接続語
14362 ワード
1365.現在の数値より小さい数値
472.接続詞
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
num_count = [0]*101
for num in nums:
num_count[num]+=1
# print(num_count)
start = 0
for i,v in enumerate(num_count):
num_count[i]=start
start+=v
# print(num_count)
result = [0]*len(nums)
for i,n in enumerate(nums):
result[i] = num_count[n]
return result
472.接続詞
from functools import lru_cache
class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
Tree = {
'children':[None]*26,'is_word':False}
result = []
for word in words:
p = Tree
for i,c in enumerate(word):
if p['children'][ord(c)-ord('a')]:
if i==len(word)-1:
p['children'][ord(c)-ord('a')]['is_word']=True
p = p['children'][ord(c)-ord('a')]
else:
tmp = {
'children':[None]*26,'is_word':False}
p['children'][ord(c)-ord('a')] = tmp
if i==len(word)-1:
tmp['is_word']=True
p = tmp
@lru_cache(None)
def dfs(index,count,word):
p = Tree
for i in range(index,len(word)):
c = word[i]
# print(word,c)
if not p['children'][ord(c)-ord('a')]:
return False
if p['children'][ord(c)-ord('a')]['is_word']:
if i==len(word)-1 and count>=1:
return True
if dfs(i+1,count+1,word) :
return True
p = p['children'][ord(c)-ord('a')]
for word in words:
if dfs(0,0,word):
result+=[word]
return result