My AC code using DP and dfs.


  • 0
    R
    class Solution:
        # @param s, a string
        # @param dict, a set of string
        # @return a list of strings
        def dfs(self,s,dct,i,dp,ret):
            if i==len(dp)-1:
                return
            m=len(dp[i])
            for j in range(m):
                    temp=[]
                    self.dfs(s,dct,dp[i][j],dp,temp)
                    if len(temp)==0:
                        ret.append(s[i:dp[i][j]])
                    else:
                        for w in temp:
                            ret.append(s[i:dp[i][j]]+" "+w)
        def wordBreak(self,s,dct):
            m=len(s)
            n=len(dct)
            ret=[]
            if m*n==0:
                return [""] if m+n==0 else ret
            DP=[[] for i in range(m+1)]
            DP[m]=["#"]
            for i in range (m-1,-1,-1):
                for j in range(i,m):
                    temp=s[i:j+1]
                    if temp in dct and len(DP[j+1])!=0:
                        DP[i].append(j+1)
            self.dfs(s,dct,0,DP,ret)
            return ret

Log in to reply
 

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