Word Break

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

For example, given

s = "leetcode", dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Notes:

1. Sequence DP
2. state: f[i] represents the string (from 0 to i) could break
3. function: f[i+1] = OR(f[j]), j from 0 to i
4. initialize: f[0] = true
5. answer: f[n]

    public boolean wordBreak(String s, Set<String> wordDict) {
        if (s == null || wordDict == null || wordDict.isEmpty()) {
            return false;
        }

        // state
        int n = s.length();
        boolean[] f = new boolean[n+1];

        // initialize
        f[0] = true;

        // function
        for (int i = 0; i < n; ++i) {
            for (int j = i; j >= 0; --j) {
                if (wordDict.contains(s.substring(j, i+1)) && f[j]) {
                    f[i+1] = true;
                    break;
                }
            }
        }

        // answer
        return f[n];
    }