Hot100 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

class Solution {
    
    public boolean wordBreak(String s, List<String> wordDict) {
    
        int n = s.length();
        HashSet<String> hashSet = new HashSet<String>();
        for(String t : wordDict)  hashSet.add(t);
        boolean[] f = new boolean[n + 1];
        f[0] = true;
        for(int i = 1; i <= n; i++){
    
            for(int j = 0; j < i; j++){
    
                String t = s.substring(j, i);
                if(f[j] == true && hashSet.contains(t)){
    
                    f[i] = true;
                    break; //有一个方案合法就可以结束了
                }
            }    
        }
        return f[n];
    }
}

作者：lin-shen-shi-jian-lu-k
链接：https://leetcode.cn/problems/word-break/solution/by-lin-shen-shi-jian-lu-k-yl5g/
来源：力扣（LeetCode）