LC 139

Solution to LeetCode 139 Word Break I.

LeetCode 139

Word Break I (Medium). [link]

1] Dynamic Programming. tmp[i] = True means the first i characters of the string can be found in wordDict. tmp[-1] = True means the string can be segmented into words and these words can be found in wordDict.

Time complexity O(n^2), space complexity O(n), where n is the length of word s.

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        n = len(s)
        tmp = [False]*(n+1)
        tmp[0] = True
        
        for i in range(n):
            for j in range(i+1, n+1):
                if (tmp[i] and (s[i:j] in wordDict)):
                    tmp[j] = True
        return tmp[-1]

Time complexity O(nm), space complexity O(n).

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        n = len(s)
        tmp = [False] * (n+1)
        tmp[0] = True
        for i in range(1, n+1):
            for w in wordDict:
                if i - len(w) >= 0 and (s[i-len(w):i] == w) and tmp[i-len(w)]:
                    tmp[i] = True
        return tmp[-1]
      
# same
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        n = len(s)
        tmp = [False] * (n+1)
        tmp[0] = True
        for i in range(1, n+1):
            for w in wordDict:
                if tmp[i] or (s[i-len(w):i] == w) and tmp[i-len(w)]:
                    tmp[i] = True
        return tmp[-1]

2] Recursion and memorization.

Works but TLE.

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        
        def DP(ss):
            if(not ss):
                return True
            res=False
            for i in range(1,len(ss)+1):
                if(ss[:i] in wordDict):
                    res=DP(ss[i:]) or res
            return res
        return DP(s)

3] Knapsack.

The main idea: for target in s, for word in wordDict, dp[i] = dp[i] or (dp[i-words] and words).

Time complexity O(nm), space complexity O(n).

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        n = len(s)
        tmp = [False]*(n+1)
        tmp[0] = True
        
        for i in range(1, len(s) + 1):
            for word in wordDict:
                tmp[i] = tmp[i] or (tmp[i - len(word)] and s[i - len(word):i] == word)
                # if tmp[i] = True, then all tmp[i] following it is True
        return tmp[-1]