처음에 dfs 로 접근하였다. 시간초과를 받고 dp 로 다시 풀었다. 시간 복잡도 O(s.length ^ 2)
class Solution:
def wordBreak(self, s: str, wordDict: list[str]) -> bool:
dict = set(wordDict)
dp = [300] * len(s)
for i in range(len(s) + 1):
for j in range(0, i):
temp = s[j: i]
if temp in dict:
if j > 0:
dp[i - 1] = min(dp[i - 1], min(dp[j - 1], j))
else:
dp[i - 1] = min(dp[i - 1], j)
return dp[-1] == 0
#Time Limit Exceeded
class Solution:
found = False
def wordBreak(self, s: str, wordDict: list[str]) -> bool:
dict = set(wordDict)
def rec(str):
if len(str) == 0:
self.found = True
for i in range(1, len(str) + 1):
if str[0: i] in dict:
rec(str[i:])
rec(s)
return self.found