# My algorithm is right? O(n^2)

• 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``````

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