why is the complexity is o(n^2)?
abcd string and worst case.
i=0, a
i=1, ab, a
i=2, abc, bc, c
i=3, abcd, bcd, cd, d
and the total operation is 10 a lot less than n^2 (16 where n=4)

@chapter Why do you say you'll remember it forever? Do you think this method is something that can used in a generic way and applied to a multitude of questions?

@dylan_yu
Thanks for sharing the java solution.
I believe the problem will be solved even without visited set. Can you give me an example for which this set will be userful ?

Beautiful Solution indeed, I rewrote the code with slight modification for corner case :
Now no need to check i-len(w)==-1

def wordBreak(self, s, wordDict):
n = len(s)
dp = [False for i in range(n+1)]//*Changed*
dp[0] = True
for i in range(1,n+1):
for w in wordDict:
if dp[i-len(w)] and s[i-len(w):i]==w://*Changed*
dp[i]=True
return dp[-1]

@www2277843987 the result will be false as it returns breakable[s.length()] and in your case breakable[10] will be false and only breakable[4] is true. and the runtime is N^2

@ivanlw It will still work without break, but I think it saves a lot of time if you break when you found a word, so you don't have to loop through the rest.

If the size of dictionary is huge, the calculations in dictionary would be a cost. If the string size is huge, the calculation would benefit. In fact, min_len can be assumed as 1, max_len may be 20. We can get the accurate answer from a real dictionary. :)

As explanation shows that "Denote dp[i] as the indicator whether s'=s[1....i] can be represented with workDict.". If we can dp[i] is true, it means that we find a solution to for combining words in wordDict into s' and we don't need to search any more.