접근

  1. dp 는 s의 현재 index를 단어의 끝으로 가장 길게 완성할 수 있는 시작 index를 가리킨다.
  2. 각 스트링 인덱스 i 마다 0부터 i까지 loop 돌며 딕셔너리에 있는지 확인한다.
  3. 딕셔너리에 있다면 그 앞선 단어와 연결되는지 확인 후 dp 업데이트 한다.
  4. i-5 ~ i 까지 이어지는 단어가 있다면 ?? ~ i-6 까지 이어진 단어가 있는지 보는식이다.

사고

처음에 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

submission