[leetcode] Word Break

Word Break

생각한 방식

1. 이중 for문을 돌면서 slice된 word가 wordDict에 있는지 확인한다.
   ⇢ O(N2)
2. start와 end로 slice된 word가 wordDict에 있으면 start와 end를 갱신하면서 s 끝까지 찾는다.
   ⇢ wordDict의 순서는 상관없기 때문에 이렇게는 풀 수 없다.
   ⇢ "leetleet"처럼 중복되서 나왔을 때 해결할 수 없다.

풀잇법

s의 끝부터 확인한다. 시작~!

노란색 화살표에 있는 문자 g로 시작하는 단어가 wordDict에 있는지 확인한다. 없다! DP[8] = F이다.

같은 방식으로 o로 시작하는 단어도 없기 때문에 DP[7] = F다.

d로 시작하는 단어로 dog가 있다. 이때 dog가 있다고 True가 되는 것이 아니라, 노란색 화살표에서 len("dog")만큼 떨어진 빨간색 화살표에 있는 곳이 True면 DP[6] = T가 된다. 이걸 왜 확인할까? 화살표가 있는 곳이 True라는 것은, 화살표가 가리키는 char로 시작하는 단어가 존재한다는 뜻이기 때문이다. 조금 헷갈린다면 뒤에 나오는 예시를 더 보자.

n으로 시작하는 단어는 없기 때문에 DP[5] = F이다.

a로 시작하는 단어로 and가 있다. 이때 len("and")만큼 떨어진 곳이 True인지 확인한다. F이므로 DP[4] = F가 된다.

🔥 DP[7] = DP[4] = T라는 것은 wordDict에 "and"와 "og"가 있었다는 뜻이다. 하지만 "og"는 발견되지 않았으므로 DP[4] = F이 된다.

s로 시작하는 sand가 있었지만 DP[7] = F이므로 DP[3] = F이다.

t로 시작하는 단어는 없었다.

a로 시작하는 and가 있었지만 ats와 달랐다.

c로 시작하는 단어는 cats와 cat이 있다. 하나씩 살펴보자.

• cats일 때는 DP[4] = F이므로 DP[0] = F이다.
• cat일 때는 DP[3] = F이이므로 DP[0] = F이다.

DP[0] = F이므로 결국 False가 리턴된다.

코드

s의 끝부터 보는 법

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        DP = [False] * (len(s)+1)
        DP[-1] = True
        
        for i in range(len(s)-1, -1, -1):
            for w in wordDict:
                if i+len(w) <= len(s) and s[i:i+len(w)] == w:
                    DP[i] = DP[i+len(w)]
                print(i, DP)
                if DP[i]: break
                
        
        return DP[0]

s의 앞부터 보는 법
i에서 시작하는 단어를 보는 게 아니라 이게 더 생각하기 복잡하다.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        DP = [False] * (len(s)+1)
        DP[0] = True
        
        for i in range(len(s)):
            for w in wordDict:
                if i-len(w)+1 >= 0 and s[i-len(w)+1:i+1] == w: 
                    DP[i+1] = DP[i-len(w)+1]
                if DP[i+1]: break
                
                    
        return DP[-1]

참고 자료

• NeetCode