Python solution in DP


  • 0
    A

    I run my DP twice because I have to check if there's at least one answer in this problem.
    Otherwise, it will get TLE.

    class Solution:
    # @param s, a string
    # @param wordDict, a set<string>
    # @return a string[]
    def wordBreak(self, s, wordDict):
        size = len(s)
        ans = []
        for i in range(size):
            ans.append([])
        
        dp = [False] * size
    
        for i in range(size):
            for j in range(i+1, size+1):
                if s[i:j] not in wordDict:
                    continue
                if i == 0 or (dp[i-1] and i>0):
                    dp[j-1] = True
        if not dp[-1]:
            return []
            
        for i in range(size):
            for j in range(i+1, size+1):
                if s[i:j] not in wordDict:
                    continue
                if i == 0 or (dp[i-1] and i>0):
                    dp[j-1] = True
                    if i == 0:
                        ans[j-1] = [s[i:j]]
                    else:
                        for tmpAns in ans[i-1]:
                            ans[j-1].append(tmpAns+' '+s[i:j])
        return ans[-1]

Log in to reply
 

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