Leetcode 139. Word Break (Trie, BFS, DP)

https://leetcode.com/problems/word-break/

Word Break - LeetCode

 

---

 

이전에 Trie의 개념과 기본 구조를 다루는 문제를 풀었었는데요

 

2022.09.27 - [Data Structure & Algorithm] - Trie (트라이, Digital tree, prefix, Retrieval tree) + 예제 코드

Trie (트라이, Digital tree, prefix, Retrieval tree) + 예제 코드

 

역시 문제를 한번 풀고서는 한번에 응용까지 가기는 쉽지 않은 것 같습니다 ㅜㅠㅜ

 

이번 문제는 사람들이 recursion, DP, Trie 등 다양한 방법으로 풀이를 해서 각 방법이

어떤 형태로 구현됐는지 알아보려합니다

 

---

 

Recursion with Memoization

  def wordBreak(self, s: str, wordDict: List[str],):
        memo = {}
        
        def memoize(target, wordDict):
            if target == "":
                return True
            if target in memo:
                return memo[target]
            
            for word in wordDict:
                if target[:len(word)] == word and memoize(target[len(word):], wordDict):
                    memo[target] = True
                    return memo[target]
            memo[target] = False
            return memo[target]
        
        return memoize(s, wordDict)

 

BFS method

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        q = deque()
        visited = set()

        q.append(0)
        while q:
            start = q.popleft()
            if start in visited:
                continue
            for end in range(start + 1, len(s) + 1):
                if s[start:end] in word_set:
                    q.append(end)
                    if end == len(s):
                        return True
            visited.add(start)
        return False

 

더 이해가 잘되는 코드로 for문으로 앞에서부터 일치하는 단어를 찾고 끝까지 찾지 못하면 False를 반환하도록 했습니다

 

Dynamic Programming

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        dp = [False] * (len(s) + 1)
        dp[0] = True

        for i in range(1, len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break
        return dp[len(s)]

 

✔ Trie 

초기에 알아보려고 했던 Trie 구조의 접근 방식입니다

 

class TrieNode:
    def __init__(self):
        self.nodes = {}
        self.is_leaf = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        cur = self.root
        for c in word:
            cur = cur.nodes.setdefault(c, TrieNode())
        cur.is_leaf = True
        
    def search(self, word):
        cur = self.root
        for c in word:
            if c not in cur.nodes:
                return False
            cur = cur.nodes[c]
        return cur.is_leaf
    

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        trie = Trie()
        for word in wordDict:
            trie.insert(word)
        dp = [False] * (len(s) + 1)
        dp[0] = True
        for i in range(1, len(s) + 1):
            for j in range(i):
                if dp[j] and trie.search(s[j:i]):
                    dp[i] = True
                    break
                    
        return dp[-1]

 

Trie구조를 만드는 것 자체는 길었지만 이후에 class 함수 호출을 통해 훨씬 더 명료하게 코드 마무리가 되는 것 같습니다.

 

 

코드를 돌려보니 Trie > Dynamic programming >memoization 순으로 Runtime이 많이나오네요

 

 

 

Source: Leetcode