一. 题目

二. 思路

• 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];
    }
}

class Solution
{
    static final int N = 310;
    boolean[] f = new boolean[N];//以i结尾的是否能拼成

    public boolean wordBreak(String s, List<String> wordDict)
    {
        int n = s.length();
        for (int i = 0; i < n; i++)
            for (String str : wordDict)
            {
                int len = str.length(), l = i - len + 1;
                if (l < 0) continue;
                if (str.equals(s.substring(l, i + 1)))
                {
                    if (l == 0) f[i] = true;
                    else f[i] |= f[l - 1];
                }
            }
        return f[n - 1];
    }
}