Leetcode 140: Word Break II

 

Code

class Solution(object):
    # For reference, this is Word Break I problem: https://czxttkl.com/?p=930
    def wordBreak1(self, s, words):
        d = [False] * len(s)    
        for i in range(len(s)):
            for w in words:
                if w == s[i-len(w)+1:i+1] and (d[i-len(w)] or i-len(w) == -1):
                    d[i] = True
        return d[-1]
    
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        # To pass a test case, I need to first check a word is breakable or not. 
        # We don't need this actually.
        if not self.wordBreak1(s, wordDict):
            return []
        self.res = []
        self.words = set(wordDict)
        self.helper(s, "")
        return self.res
        
    def helper(self, s, concat):
        for i in xrange(1, len(s)+1):
            if s[0:i] in self.words:
                concat_cp = concat + ' ' + s[0:i]
                if i == len(s):
                    # strip to remove first ' '
                    self.res += [concat_cp[1:]]
                else:
                    self.helper(s[i:], concat_cp)
                    
                    

 

Idea:

DFS essentially. The time complexity is O(3^N), where N is the length of s. How to get this time complexity?

T(1)=T(1)

T(2)=(T(1)+T(1))+T(1) = 3T(1)     # Check if the first character and the second character are words in the dictionary, or check    
                                  # if the whole two characters form a word in the dictionary

T(3) = (T(1)+T(2))+(T(2)+T(1))+T(1) # Check if the first character and the last two characters are words in the dictionary, or 
                                    # check if the first two characters and the last character are words in the dictionary, or 
                                    # check if the whole three characters form a word in the dictionary. 
...
T(N) = (T(1)+T(N-1))+(T(2)+T(N-2))+...+(T(N-1)+T(1))+T(1)
     = 3T(N-1)

Since the time complexity is exponential, leetcode doesn’t pass my code for certain test cases. I added the function from Word Break I to first check if a word is breakable. If yes, then I continue to generate return strings. In this way I passed the leetcode OJ.

 

To alleviate the duplication of computation, we can use dynamic programming idea to have more space in trade of the time. But I don’t think it can alleviate the time complexity of the worst case.

Code (https://leetcode.com/discuss/64513/python-dp-solution-in-11-lines):

def wordBreak(self, s, wordDict):
    """
    :type s: str
    :type wordDict: Set[str]
    :rtype: List[str]
    """
    M = {}
    def dfs(remain_str):
        if not remain_str: return ['']
        if remain_str in M: return M[remain_str]
        ret = []    
        for i in xrange(1,len(remain_str)+1):
            if remain_str[:i] in wordDict: 
                for r in dfs(remain_str[i:]): 
                    ret.append( (remain_str[:i]+' '+r).strip() )
        M[remain_str] = tuple(ret)
        return ret
    return dfs(s)