A/C Python solution, DP, easy to understand


  • 0
    W
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        #print "s = ", s
        lenS = len(s)
        #print "lenS = ", lenS
    
        data2D = [[False for i in range(lenS )] for j in range(lenS )]
    
        for l in range(1, lenS+1):
            #print "l = ", l
    
            for i in range(lenS):
                tmpS = s[i:i+l]
                #print "i = ", i, "i+l = ",i+l, " tmpS = ", tmpS
    
                if (i + l) > (lenS):
                    continue
    
                if tmpS in wordDict:
                        data2D[i][i+l-1] = True
                        #print "found word ", tmpS
    
                else:
                    #do the break
                    for breakPoint in range(l):
                        #print "breakPoint = ",breakPoint
                        firstS = tmpS[i:breakPoint]
                        secondS = tmpS[breakPoint:i+l]
                        #print "firstS = ", firstS, " secondS = ", secondS
                        #print "i = ", i, " i+breakPoint = ", i+breakPoint, " i+l-1 = ", i+l-1
                        if data2D[i][i+breakPoint-1] == True and data2D[i+breakPoint][i+l-1] == True:
                            data2D[i][i + l - 1] = True
    
        #print "data2D = ", data2D
        #print "data2D[0][-1] = ", data2D[0][-1]
        return data2D[0][-1]

Log in to reply
 

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