dynamic programming for great win. Problem: putting spaces back into a string of words.

gistfile1.txt

obamasaysheplanstovetothebillinmanhattan 

router
doesnt
suck
haha
this
is
more
words
obama

n = length of string
m = number of words in dictionary
l = average length of word

m^(n/l)

m*n*n^2*(n/l)

(n) + (n - 1) + (n - 2) + ... + (0)

# n^2 (startindex,endindex) pairs, memoize all n^2 lookups.
F("") = TRUE
F(string) = any([ string.substring(0,i).isInDictionary() and F(string.substring(i,len(string))) 
						     for i in range len(string)])