[Leetcode] 139. Word Break

문제 바로가기

Tree + DFS + DP

tree를 생성해 DFS를 진행했다. 그 과정에서 중복되는 계산을 줄이기 위해 DP를 적용했다.

Recursion

class Node:
    def __init__(self, isLeaf: bool = False):
        self.isLeaf = isLeaf
        self.children = dict()

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordTree = Node()
        visited = set()
        leng = len(s)
        for word in wordDict:
            head = wordTree
            for c in word:
                if c not in head.children:
                    head.children[c] = Node()
                head = head.children[c]
            head.isLeaf = True
        
        def DFS(i: int, head: Node):
            if i == leng:
                return True if head.isLeaf else False
            
            res = False
            if head.isLeaf and s[i:] not in visited:
                visited.add(s[i:])
                res = res or DFS(i, wordTree)
            
            if s[i] in head.children:
                res = res or DFS(i + 1, head.children[s[i]])
            elif not head.isLeaf:
                return False
            return res
        
        return DFS(0, wordTree)

Iteration

class Node:
    def __init__(self, isLeaf: bool = False):
        self.isLeaf = isLeaf
        self.children = dict()

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordTree = Node()
        visited = set()
        leng = len(s)
        for word in wordDict:
            head = wordTree
            for c in word:
                if c not in head.children:
                    head.children[c] = Node()
                head = head.children[c]
            head.isLeaf = True
        
        stack = [0]
        while stack:
            idx = stack.pop()
            head = wordTree
            while idx < leng and s[idx] in head.children:
                if head.isLeaf and s[idx:] not in visited:
                    stack.append(idx)
                    visited.add(s[idx:])
                head = head.children[s[idx]]
                idx += 1
            if idx == leng and head.isLeaf:
                return True
            if head.isLeaf and s[idx:] not in visited:
                stack.append(idx)
                visited.add(s[idx:])
        return False

BFS + DP

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 이미 break했던 word의 set
        visited = set()
        q = deque([s])
        
        while q:
            curString = q.popleft()
            
            if curString == "":
                return True
            
            for word in wordDict:
                l = len(word)
                if curString[0:l] == word and curString[l:] not in visited:
                    q.append(curString[l:])
                    visited.add(curString[l:])
        return False