Example: Word Break Problem

You are given a string and a dictionary, you have to tell if the string can be split into one or more words such that each word belong in the dictionary.

X = I am ace

---	I	a	m	a	c	e
---	0	1	2	3	4	5
0	T	T	T	T	F	T
1		T	T	T	F	T
2			F	F	F	F
3				T	F	T
4					F	F
5						F

• for l = 1 => 1 char at a time
• for l > 1 =>
  • if x[i..j] is in dictionary d[i,j] = T
  • if split k such that x[i..k] == T && x[k+1,j] == T exists then d[i,j] = T

// x[i..j] == string made of characters from i to j
wordSplit(x,d)
    n = x.len
    let d[0..n-1, 0..n-1] be tables, init s to False
    s[0..n-1, 0..n-1] be tables, init s to -1
    for i = 0 to  n-1
        if x[i..i] in dict
            d[i,i] = T
            s[i,i] = -1
    for l = 2 to x.len
        for i = 0 to n - l
            j = i + l - 1
            if x[i..j] in dict
                d[i,j] = T
                s[i,j] = -1
            else   0 1 2
                for k = i to j-1
                    if d[i,k] == T && d[k+1, j] == T
                        d[i,j] = T
                        s[i,j] = k
                        break
     printResult(d, s, x, 0, n-1)

// if s[i,j] == -1 entire word was considered otherwise check d[i,k] and d[k+1, j]
printResult(d, s, x, i, j) 
     k = s[i, j] 
     if k == -1
         print(x[i..j])
     else 
         printResult(d, s, x, i, k)
         printResult(d, s, x, k + 1, j)