一. 题目

二. 思路

• f[i]:以i结尾的字符串是否能拼成。

• f[0]=true.（1~n）

• 枚举上一个状态，然后判断中间差值是否字典中存在

三. 代码

class Solution
{
    static final int N = 310;
    boolean[] f = new boolean[N];

    public boolean wordBreak(String s, List<String> wordDict)
    {
        int n = s.length();
        String ns = "!" + s;
        Set<String> words = new HashSet<>(wordDict);

        f[0] = true;
        for (int i = 1; i <= n; ++i)//当前位置
            for (int j = 0; j < i; ++j)//前一个位置
                f[i] |= f[j] & words.contains(ns.substring(j + 1, i + 1));
        return f[n];
    }
}