Word Break

Problem

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Example

Given s = "lintcode", dict = ["lint", "code"].

Return true because "lintcode" can be break as "lint code".

Code - Java

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {

        int size = s.length();
        boolean[] flag = new boolean[size];

        for (int i = 0; i < size; i++) {
            if (i == 0 || flag[i - 1] == true) {
                for (int j = i; j < size; j++) {
                    if (dict.contains(s.substring(i, j + 1))) {
                        flag[j] = true;
                    }
                }
            }
        }
        return flag[size - 1];
    }
}

public class Solution {
    /**
     * @param s:    A string s
     * @param dict: A dictionary of words dict
     */
    public boolean wordBreak(String s, Set<String> dict) {
        int len = s.length();
        if (len == 0) return true;
        boolean[] flag = new boolean[len];
        flag[0] = true;

        for (int i = 0; i < len; i++) {
            if (flag[i] == false) {
                continue;
            }
            for (String word : dict) {
                int j = i, k = 0, l = word.length();

                while (j < len && k < l && s.charAt(j) == word.charAt(k)) {
                    j++;
                    k++;
                }

                if (k == l) {
                    if (j == len) {
                        return true;
                    } else {
                        flag[j] = true;
                    }
                }
            }
        }
        return false;
    }
}