[139. Word Break] #leetcode

139_1014.py

# memo string
class Solution(object):
    def __init__(self):
        self.memo = dict()
        
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        if not s:
            self.memo[s] = True
            return True
        
        if s in self.memo:
            return self.memo[s]
        
        for i in range(len(s)):
            if s[:i+1] in wordDict and self.wordBreak(s[i+1:], wordDict):
                self.memo[s] = True
                return True
        
        self.memo[s] = False
        return False
      
# memo start index
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        memo = dict()
        return self.dfs(s, set(wordDict), 0, memo)
    
    def dfs(self, s, wordDict, start, memo):
        if start == len(s):
            return True
        
        if start in memo:
            return memo[start]
        
        for end in range(start+1, len(s)+1):
            if s[start:end] in wordDict and self.dfs(s, wordDict, end, memo):
                memo[start] = True
                return True
        
        memo[start] = False
        return False
      
      
# dp 
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        wordSet = set(wordDict)
        dp = [False for i in range(len(s)+1)]
        
        # empty is True
        dp[0] = True
        
        # loop from 1 to len+1
        for i in range(1, len(s)+1):
            for j in range(i):
                # string 0 to i, split into 0 to j, and j+1 to i
                # since it's not zero based array, so we use [j:i]
                if dp[j] and s[j:i] in wordSet:
                    dp[i] = True
                    break
        
        # return 
        return dp[len(s)]