Unexpectedly Beats 100% Python Solution (Dynamic Programming & Backtracking)


  • 0
    J
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: Set[str]
            :rtype: List[str]
            """
            from copy import deepcopy
            
            
            if not s or not wordDict:
                return []
    
            min_len, max_len = float('inf'), float('-inf')
            for word in wordDict:
                min_len = min(min_len, len(word))
                max_len = max(max_len, len(word))
                
            # dp.
            n = len(s)
            dp = [False] * n
            start = [[] for i in xrange(n)]
            for end_index in xrange(min_len - 1, n):
                start_index = end_index - min_len + 1
                while start_index >= 0 and end_index - start_index + 1 <= max_len:
                    word = s[start_index : end_index + 1]
                    if word in wordDict and (start_index == 0 or dp[start_index - 1]):
                        dp[end_index] = True
                        start[end_index].append(start_index)
                    start_index -= 1
            
            # bt: construct result.
            def helper(s, dp, start, end_index, res, ass):
                if end_index >= 0:
                    for start_index in start[end_index]:
                        word = s[start_index : end_index + 1]
                        ass2 = deepcopy(ass)
                        if not ass2:
                            ass2.append([word])
                        else:
                            for a in ass2:
                                a.append(word)
                        if start_index == 0:
                            for a in ass2:
                                a.reverse()
                                res.append(' '.join(a))
                        else:
                            helper(s, dp, start, start_index - 1, res, ass2)
                return None
                        
            res = []
            helper(s, dp, start, n - 1, res, [])
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.