My algorithm is right? O(n^2)


  • 0
    L

    Based on Word Break, I record all the possible paths in dp process. and then output the result. TLE in test data s = "aaaaaaaaaaaaaa..." dict = {"a","aa","aaa","aaaa"...}. there is something wrong with my code? the time complexity of output is limited?

    def getList(self, now, path, end):
        if now >= end:
            self.result.append(self.one)
            return
        for pat in path[now]:
            self.one.append(pat)
            self.getList(pat,path,end)
            self.one = self.one[:-1]
    def wordBreak(self, s, dict):
        dp = [False for j in range(len(s)+1)]
        path = [ [] for j in range(len(s)+1)]
        dp[0] = True
        for i in range(len(s)):
            for j in range(i+1)[::-1]:
                #print i,j,s[j:i+1]
                if (s[j:i+1] in dict) and dp[j] == True:
                    dp[i+1] = True
                    path[j].append(i+1)
        self.result = []
        self.one = []
        self.getList(0,path,len(s))
        #print self.result
        result = []
        for items in self.result:
            one = ""
            start = 0
            for item in items:
                one += s[start:item]+" "
                start = item
            result.append(one.strip())
        return result

Log in to reply
 

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