动态规划 · 拆分词句

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        if (s == null || s.length() == 0) return false;
        // dp[n] 代表着 ：字符串前 N 个字符能否被 Dict 拆分
        boolean[] dp = new boolean[s.length() + 1];
        // 空集可以被 dict 拆分
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            // 确保前 0 - i- 1之间每种方案都可以被拆分
            for (int j = i - 1; j >= 0; j--) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}