Given a dictionary of words an... | CareerCup

Given a dictionary of words an... | CareerCup: "Given a dictionary of words and a string with all spaces removed, return whether the string is composed of valid words
e.g
helloworld-> hello world (valid)
isitniceinhere-> is it nice in here (valid)
zxyy-> invalid
Using dynamic programming I got an O(n3) algorithm but he insisted on an O(n2), any idea?"

function getValidWords(i) returns [list, boolean]
  if we have reached end of the string
     return [empty_list, true]
  
let js = start from index i, find an array of j's
     such that the span [i, j] is a valid word.
  
for each j in js
     let [lista, boola] = getValidWords(j)
     if boola is true then
        let listb = span[i, j] ++ lista
        return [listb, true]
     else
        return [empty_list, false]
  end for
end function