문제

• 문자열 s
• 리스트 wordDict
• wordDict의 단어로 s가 구성되어 있으면 true

풀이

replace로 접근

• 문자열 같아서 replace 해봄

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        for word in wordDict:
            s = s.replace(word, "")
            
        if s:
            return False
        else:
            return True

이런 경우 오류가 난다. 순서때문에...

DP

• 아 그래서 분류가 DP였구나.......
• 이모저모로 matrix 그려봤는데 모르겠다

recursion

• 그냥 recursion으로 풀면!?

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        global ans
        ans = False
        wordLen = dict()
        for word in wordDict:
            wordLen[word] = len(word)
            
        recursion(s, wordLen)
        return ans

        
        
def recursion(s, wordLen):
    global ans
    if not s:
        # break condition
        ans = True
        return 
    for word, length in zip(wordLen, wordLen.values()):
        if s[:length] == word:
            recursion(s[length:], wordLen)

젠장.......

bfs

from collections import deque

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        global ans
        ans = False
        wordLen = dict()
        for word in wordDict:
            wordLen[word] = len(word)
        
        # bfs
        q = deque()
        q.append(s)
        visited = set()
        while q:
            thisS = q.popleft()
            if thisS == "":
                return True
            for word, wLen in zip(wordLen, wordLen.values()):
                if thisS[:wLen] == word:
                    if thisS[wLen:] not in visited:
                        visited.add(thisS[wLen:])
                        q.append(thisS[wLen:])
        
        return False

visited 없을 땐 안됐는데, visited쓰니까 바로 통과됐다

심지어 속도 미쳤음....
어이없네.....