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".

example: "abc"

f[3] = f["abc"]

f[2] = f["ab"]

f[1] = f["a"]

f[0] = f[""]

思路:

• 一个长度为n的单词, 假设i 为某一位, 能否切分成词典里面的词, 取决于 长度(0 到 i) 子串是否能成功切分, 并且(i 到 n) 子串是词典里面的单词.
• 所以我们定义
• state:
  • f[i]: 前i个字符能被切分为dict words
  • size: n + 1
• function:
  • f[i]: j < i, f[j] && substring(i, n) in dictionary
• initialize:
  • f[0]: true, empty string
• answer:
  • f[n]
• 时间复杂度
  • O(l * n^2)
  • l is the average length of words in dict

    public boolean wordBreak(String s, Set<String> dict) {
        if (s == null) {
            return false;
        }  

        boolean[] dp = new boolean[s.length() + 1];

        dp[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] == false) continue;

                if (dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }

Optimization

假设给定的字符串很长, j 所取的长度便会很大, 导致时间复杂度很高. 于是我们遍历字典, 找到最长的单词长度

i - j <= maxWordLength, 并且j 从 i - 1开始取, j >= 0

时间复杂度: O(n * l ^ 2)

    public boolean wordBreak(String s, Set<String> dict) {
        if (s == null) {
            return false;
        }  

        boolean[] dp = new boolean[s.length() + 1];

        dp[0] = true;

        int maxLen = getMaxLength(dict);

        for (int i = 1; i <= s.length(); i++) {
            for (int j = i - 1; i - j <= maxLen && j >= 0; j--) {
                if (dp[j] == false) 
                    continue;

                if (dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }

    private int getMaxLength(Set<String> dict) {
        int res = Integer.MIN_VALUE;
        for (String s: dict) {
            res = Math.max(res, s.length());
        }
        return res;
    }