Python solution beats 100% using DP!


  • 0
    H

    Alright I admit my solution is just combine the answers for two question together. I just can not prevent myself from show off my first beat-100-person solution :D

    just kidding~

    class Solution(object):
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: Set[str]
            :rtype: List[str]
            """
            if not s or not wordDict or not self.breakable(s, wordDict): return []
            word_len, start = max(map(len, wordDict)), min(map(len, wordDict)) - 1
            dp = [[] for i in xrange(len(s)+1)]
            dp[0].append('')
            for i in xrange(start, len(s)):
                for j in xrange(start+1, 1+min(word_len, i+1)):
                    if s[i-j+1:i+1] in wordDict:
                        if i+1-j != 0 and dp[i+1-j]:
                            dp[i+1] += [each + ' ' + s[i-j+1:i+1] for each in dp[i+1-j]]
                        elif i+1-j == 0:
                            dp[i+1].append(s[i-j+1:i+1])
            # print dp
            return dp[-1]
        def breakable(self, s, wordDict):
            """
            :type s: str
            :type wordDict: Set[str]
            :rtype: bool
            """
            if not s or not wordDict: return False
            word_len, start = max(map(len, wordDict)), min(map(len, wordDict)) - 1
            dp = [0 for i in xrange(len(s)+1)]
            dp[0] = 1
            for i in xrange(start, len(s)):
                for j in xrange(start+1, 1+min(word_len, i+1)):
                    # print s[i-j+1:i+1]
                    if s[i-j+1:i+1] in wordDict:
                        dp[i+1] += dp[i+1-j]
                        if dp[i+1] > 0: break
                # print dp
            # print dp
            return dp[-1] > 0
    

Log in to reply
 

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