Word break

Given a set of words concatenated together, break them apart.

Solution

• Keep an array to keep track of all breaking points and the length to break them by
• Start from index 0 and check if 0..i is a valid word, if it is then mark T[i] = i + 1, this is the first word
• Now check j = 0..i for any previous word breaks that were identified
  • if T[j] != 0 and if str[j+1..i] is a valid word, then set T[i] = i-j
  • repeat this until end of the string

Code

def word_break(str)
    for i in 0..str.len do
        # Find first word
        if valid_word?(str[0..i])
            T[i] = i+1
        end

        # Find subsequent words till end of the string
        for j in 0..i do
            if T[j] != 0 && valid_word?(str[j+1..i])
                T[i] = i-j
            end
        end
    end

    # Print words as sentences
    i = t.size
    while i>=0 
        if i != 0
            result << str[i-t[i]..i] # extract word
        end
        i -= 1
    end
end

Time Complexity

O(n^3)