leetcode 140
This is pretty much an easier version of Palindrome Partitioning, cuz finding a word is much easier than finding a valid palindrome substring.
Using a backtracking method:
- When a substring is breakable, we iterate this substring and find all possible break positions.
- Dfs search each possible breaks.
- If search ends, we find a match.
Corner Cases:
We can handle the situaion which search string is '', so we can put the terminal condition in the self.breakable()
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
|
class Solution:
def breakable(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False]*(n+1)
dp[0] = True
for i in range(1, n+1):
for n in range(i+1):
if dp[n] and s[n:i] in wordDict:
dp[i] = True
break
return dp[n]
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
n = len(s)
results: List[str] = []
def search(i:int, path: List[str]):
if i == n:
results.append(' '.join(path))
if self.breakable(s[i:], wordDict):
for j in range(i, n):
sub_str = s[i:j+1]
if sub_str in wordDict:
search(j+1, path+[sub_str])
search(0, [])
return results
|