# 139. word Break
###### tags: `leetcode` `medium`
## problem
**input**
"cars"
"ccbb"
"ccaccc"
"goalspecial"
"catscatdog"
"ddadddbdddadd"
**output**
["car","ca","rs"]
["bc","cb"]
["cc","ac"]
["go","goal","goals","special"]
["cat","cats","dog"]
["dd","ad","da","b"]
## Solution
使用DP。(bottom up)
沒想到直接看答案。
f[i]代表s[:i]是可以被wordDict所組成的。
$$
f(i) =
\begin{cases}
True & \text{if $i$ = 0} \\
True, & \text{if $f(i-len(w_j))$ = True AND $w_j$ in
dict} \\
False, & \text{otherwise}
\end{cases}
$$
Time complexity:
$$
O \bigl( n^2 \bigr)
$$
Runtime | Memory Usage
--- | ---
54.17% | 5.55%
```py=
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
d = set(wordDict)
f = [False for i in range(len(s)+1)]
f[0] = True
for i in range(1, len(s)+1):
for j in range(i):
if f[j] and s[j:i] in d:
f[i] = True
break
return f[len(s)]
```
## Solution
使用暴力法
Time complexity:
$$
O \bigl( n^2 \bigr) ??
$$
Runtime | Memory Usage
--- | ---
636 ms | 15.1 MB
5.56% | 5.14%
有想法就幹，try and error
測資全過，可能有其他未知bug
## 結構一
想法1:
從字典中找到目標字串存在的詞(word)，用while刪除目標字串中所有word，並以","分隔，每次刪完word，皆做判斷是否只剩最後一個詞且字典中有對應之字詞，若可即判斷True，或者將其刪到只剩","也判斷True
想法2:
字串長度有長有短，若字典將目標s刪到小於需要對應知字典詞(word)的長度，將目標s還原成刪除前的樣子i.e. s = tmp，之後再作刪除，每次刪完word，皆做判斷是否只剩最後一個詞且字典中有對應之字詞，若可即判斷True
想法3:
疊字爭議，根據經驗字典中的疊字丟到字典之後，以repeateddic分開後，到最後在刪除判斷，會正確且容易分析出字串的結構
<前三個想法組成結構一>
-----
想法4:
因為目標字是由字典所構成，目標之第一個字詞或最後一個字詞，一定也在字典之中，因此我依序刪除第一個、最後一個使原始字串(tmp)修整之後，再進行與結構(一)相同的判斷
想法5:
改變字典的刪除順序影響結果，checkIgnore 若以長度長的排前面，出現疊字丟入字典最末，若字典長度相同，將所有除疊字以外長度相同之字典字詞，進行交換，形成所有組合，並一一判斷。
若以上皆無找到字典詞組合可形成目標字串即判斷False
```py=
def wordBreak(s, wordDict):
tmp = s
splitCount = 0
repeateddic = []
checkIgnore = []
removeFromCheckIgnore = []
for word in wordDict:
if s != tmp:
checkIgnore.append(word)
'''if word.count(word[0])==len(word) and len(word)>1:
repeateddic.append(word)'''
if len(s) >= len(word)+splitCount:
if s.find(word)!=-1:
#print("replace")
#print(word)
while s.find(word)!=-1:
s = s.replace(word,",",1)
splitCount += 1
lastelement = 2
for x in s.split(","):
if x in set(wordDict):
lastelement = 1
elif x == "":
pass
else:
lastelement = 0
break
if lastelement == 1:
return True
#print(s)
#print(splitCount)
if len(s) == splitCount:
return True
elif s == tmp and s.find(word)==-1:
removeFromCheckIgnore.append(word)
else:
pass
else:
s = tmp
#print(s)
splitCount = 0
if s.find(word)!=-1:
while s.find(word)!=-1:
s = s.replace(word,",",1)
splitCount += 1
for x in s.split(","):
if x in set(wordDict):
lastelement = 1
elif x == "":
pass
else:
lastelement = 0
break
if lastelement == 1:
return True
#print(s)
#print(splitCount)
if len(s) == splitCount:
return True
for word in repeateddic:
if s.find(word)!=-1:
while s.find(word)!=-1:
s = s.replace(word,",",1)
splitCount += 1
for x in s.split(","):
if x in set(wordDict):
lastelement = 1
elif x == "":
pass
else:
lastelement = 0
break
if lastelement == 1:
return True
#print(s)
#print(splitCount)
if len(s) == splitCount:
return True
#print("remove")
#print(removeFromCheckIgnore)
for garbage in removeFromCheckIgnore:
if garbage in checkIgnore:
checkIgnore.remove(garbage)
while len(checkIgnore) != 0:
#print(checkIgnore)
s = tmp
splitCount = 0
for word in checkIgnore:
if len(s) >= len(word)+splitCount:
if s.find(word)!=-1:
while s.find(word)!=-1:
s = s.replace(word,",",1)
splitCount += 1
lastelement = 2
for x in s.split(","):
if x in set(wordDict):
lastelement = 1
elif x == "":
pass
else:
lastelement = 0
break
if lastelement == 1:
return True
#print(s)
#print(splitCount)
if len(s) == splitCount:
return True
else:
pass
else:
s = tmp
#print(s)
splitCount = 0
if s.find(word)!=-1:
while s.find(word)!=-1:
s = s.replace(word,",",1)
splitCount += 1
#print(s)
#print(splitCount)
lastelement = 2
for x in s.split(","):
if x in set(wordDict):
lastelement = 1
elif x == "":
pass
else:
lastelement = 0
break
if lastelement == 1:
return True
if len(s) == splitCount:
return True
for word in repeateddic:
if s.find(word)!=-1:
while s.find(word)!=-1:
s = s.replace(word,",",1)
splitCount += 1
lastelement = 2
for x in s.split(","):
if x in set(wordDict):
lastelement = 1
elif x == "":
pass
else:
lastelement = 0
break
if lastelement == 1:
return True
#print(s)
#print(splitCount)
if len(s) == splitCount:
return True
del checkIgnore[0]
tmp2 = tmp
for r in range(len(wordDict)):
tmp = tmp2
#print("wordDict[r] = ",wordDict[r])
if tmp.find(wordDict[r])==0 or tmp.rfind(wordDict[r])==len(tmp)-len(wordDict[r]):
tmp = tmp.replace(wordDict[r],"",1)
else:
continue
s = tmp
#print("tmp = ",tmp)
splitCount = 0
repeateddic = []
checkIgnore = []
removeFromCheckIgnore = []
for word in wordDict:
if s != tmp:
checkIgnore.append(word)
if word.count(word[0])==len(word) and len(word)>1:
repeateddic.append(word)
continue
if len(s) >= len(word)+splitCount:
if s.find(word)!=-1:
#print("replace")
#print(word)
while s.find(word)!=-1:
s = s.replace(word,",",1)
splitCount += 1
lastelement = 2
for x in s.split(","):
if x in set(wordDict):
lastelement = 1
elif x == "":
pass
else:
lastelement = 0
break
if lastelement == 1:
return True
#print(s)
#print(splitCount)
if len(s) == splitCount:
return True
elif s == tmp and s.find(word)==-1:
removeFromCheckIgnore.append(word)
else:
pass
else:
s = tmp
#print(s)
splitCount = 0
if s.find(word)!=-1:
while s.find(word)!=-1:
s = s.replace(word,",",1)
splitCount += 1
#print(s)
#print(splitCount)
if len(s) == splitCount:
return True
for word in repeateddic:
if s.find(word)!=-1:
while s.find(word)!=-1:
s = s.replace(word,",",1)
splitCount += 1
#print(s)
#print(splitCount)
if len(s) == splitCount:
return True
#print("remove")
#print(removeFromCheckIgnore)
# for garbage in removeFromCheckIgnore:
# if garbage in checkIgnore:
# checkIgnore.remove(garbage)
for w in wordDict:
#print(w)
#print(not w in set(checkIgnore))
if not w in set(checkIgnore) and not w in set(repeateddic):
checkIgnore.append(w)
else:
pass
#print("remove")
#print(removeFromCheckIgnore)
for garbage in removeFromCheckIgnore:
if garbage in checkIgnore:
checkIgnore.remove(garbage)
checkIgnore_revise = [(0,0)]*len(checkIgnore)
for i in range(len(checkIgnore)):
checkIgnore_revise[i] = [len(checkIgnore[i]),i]
checkIgnore_revise.sort()
checkIgnore_2 = [""]*len(checkIgnore)
for x in range(len(checkIgnore)):
checkIgnore_2[x] = checkIgnore[checkIgnore_revise[len(checkIgnore)-1-x][1]]
#print("checkIgnore_2 = ",checkIgnore_2)
repeatedwords = 0
checkIgnore_3 = [a for a in checkIgnore_2]
for o in checkIgnore_2:
if o.count(o[0])==len(o) and len(o)>1:
checkIgnore_3.remove(o)
checkIgnore_3.append(o)
repeatedwords += 1
else:
pass
checkIgnore_4 = []
checkIgnore_4.append(checkIgnore_3)
for u in range(len(checkIgnore_3)-repeatedwords):
for v in range(1,len(checkIgnore_3)-repeatedwords):
if len(checkIgnore_3[u]) == len(checkIgnore_3[v]) and len(checkIgnore_3[u])>1 and u!=v:
#print("u,v = ",u,v )
checkIgnore_3[u],checkIgnore_3[v] = checkIgnore_3[v],checkIgnore_3[u]
#print(checkIgnore_3)
checkIgnore_5 = [q for q in checkIgnore_3]
checkIgnore_4.append(checkIgnore_5)
checkIgnore_3[u],checkIgnore_3[v] = checkIgnore_3[v],checkIgnore_3[u]
#print("checkIgnore_4=",checkIgnore_4)
for g in range(len(checkIgnore_4)):
while len(checkIgnore_4[g]) != 0:
#print(checkIgnore_4)
s = tmp
splitCount = 0
for word in checkIgnore_4[g]:
if len(s) >= len(word)+splitCount:
if s.find(word)!=-1:
while s.find(word)!=-1:
s = s.replace(word,",",1)
splitCount += 1
lastelement = 2
for x in s.split(","):
if x in set(wordDict):
lastelement = 1
elif x == "":
pass
else:
lastelement = 0
break
if lastelement == 1:
return True
#print(s)
#print(splitCount)
if len(s) == splitCount:
return True
else:
pass
else:
s = tmp
#print(s)
splitCount = 0
if s.find(word)!=-1:
while s.find(word)!=-1:
s = s.replace(word,",",1)
splitCount += 1
lastelement = 2
for x in s.split(","):
if x in set(wordDict):
lastelement = 1
elif x == "":
pass
else:
lastelement = 0
break
if lastelement == 1:
return True
#print(s)
#print(splitCount)
if len(s) == splitCount:
return True
for word in repeateddic:
if s.find(word)!=-1:
while s.find(word)!=-1:
s = s.replace(word,",",1)
splitCount += 1
lastelement = 2
for x in s.split(","):
if x in set(wordDict):
lastelement = 1
elif x == "":
pass
else:
lastelement = 0
break
if lastelement == 1:
return True
#print(s)
#print(splitCount)
if len(s) == splitCount:
return True
del checkIgnore_4[g][0]
return False
```
Sign in with Wallet
Connect another wallet