-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
691.py
73 lines (70 loc) · 2.48 KB
/
691.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
__________________________________________________________________________________________________
sample 64 ms submission
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
'''
1. each time, creat a new lev to store the target that has deleted the letters in the stickers.
2.if new_t = '',return count
'''
if not target:
return 0
tmp=[]
for s in stickers:
dic={}
for c in s:
dic[c]=dic.get(c,0)+1
tmp.append(dic)
stickers=tmp
lev=[target]
count=1
seen={target}
while lev:
new_lev=[]
for t in lev:
for s in stickers:
if t[0] in s:
new_t=t
for c in s:
new_t=new_t.replace(c,'',s[c])
if new_t=='':
return count
if new_t not in seen:
seen.add(new_t)
new_lev.append(new_t)
count+=1
lev=new_lev
return -1
__________________________________________________________________________________________________
sample 13288 kb submission
import sys
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
m = len(stickers)
mp = [[0]*26 for y in range(m)]
for i in range(m):
for c in stickers[i]:
mp[i][ord(c)-ord('a')] += 1
dp = {}
dp[""] = 0
def helper(dp, mp, target):
if target in dp:
return dp[target]
n = len(mp)
tar = [0]*26
for c in target:
tar[ord(c)-ord('a')] += 1
ans = sys.maxsize
for i in range(n):
if mp[i][ord(target[0])-ord('a')] == 0:
continue
s = ''
for j in range(26):
if tar[j] > mp[i][j]:
s += chr(ord('a')+j)*(tar[j] - mp[i][j])
tmp = helper(dp, mp, s)
if (tmp != -1):
ans = min(ans, 1+tmp)
dp[target] = -1 if ans == sys.maxsize else ans
return dp[target]
return helper(dp, mp, target)
__________________________________________________________________________________________________