登录
  • #刷题
  • #leetcode

上一‌‌‍‍‌‍‍‌‍‍‌‌‌‌‌‍‍‌‍‌‍‍‌‌‌‌‌‍‍‌‌‍周Contest最后一题,LC1307,为什么我prun后还是TLE,求问

wowowonini
541
0
下面是代码及注释:

class Solution:

def isSolvable(self, words: List[str], result: str) -> bool:

dic = {}

for i in words:

for j in i:

if j not in dic:

dic[j] = 0

for i in result:

if i not in dic:

dic = 0 #建立hashmap,每个字母对应一个数字

keys = list(dic)

head = set() #建立头set,用于保证每个单词的开头字母不能为0

def dfs(pos,Set):

if pos == len(keys): #检测是否成立,逐层比较prun

cy = 0

p = -1

while -p<=len(result):

left = 0

for i in words:

if -p<=len(i):

left+=dic[i[p]]

div,mod = left//10,left%10

left = mod+cy

cy = div

right = dic[result[p]]

if left != right:

return False

p-=1

return True

count = 0

while count<len(Set): #给所有字母分配数字

if keys[pos] in head: #头字母不能为0

if Set[0] == 0:

if len(Set) == 1:

return False

Set.append(Set.popleft())

dic[keys[pos]] = Set.popleft()

if dfs(pos+1,Set):

return True

else:

Set.append(dic[keys[pos]])

count+=1

return False

queue = collections.deque()

for i in range(10):

queue.append(i)

return dfs(0,queue)

第三个test case就TLE了["LEET","CODE"],"POINT"

我自己在shell中测试了一下,加上检测和递归,总共也就跑了18000000次左右,感觉远比不prun的(4+4+5)*10!要好很多了,但是还是TLE了。是prun的方式不对吗?
0条回复
热度排序

发表回复