leetcode139:单词拆分

package com.mxnet;

import java.util.HashSet;
import java.util.List;

public class Solution139 {

    public static void main(String[] args) {

    }

    /**
     * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
     *
     * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用
     * @param s
     * @param wordDict
     * @return
     * 思路：动态规划
     * 1. 首先使用hash结构判断字符串是否被包含在集合中
     * 2. 遍历字符串中的每一个字符，取出以这个字符为结尾的所有子串
     * 3. 判断所有子串是否包含在hash集合中
     * 4. 使用Boolean数组保存当前位是否可以被拼接
     * 5. 若某一子串在集合中，则将其所在Boolean数组所在为置为true
     * 6. 遍历完所有字符时，若Boolean数组最后一位为true，说明可以被拼接
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        //使用hash结构判断字符串子串是否被包含
        HashSet<String> hashSet = new HashSet<>(wordDict);
        //使用boolean类型数组判断某一位字符是否被包含
        boolean[] isConcat = new boolean[s.length() + 1];
        //初始空串默认被包含
        isConcat[0] = true;
        //遍历字符串每一位字符，并判断由其组成的子串是否包含在集合中
        for (int i = 1; i <= s.length(); i++) {
            //遍历该字符前的所有子串
            for (int j = 0; j < i; j++) {
                //如果某一子串被包含，则将相应位置置为true
                if (isConcat[j] && hashSet.contains(s.substring(j,i))){
                    isConcat[i] = true;
                    break;
                }
            }
        }
        //若最后一位也为true,说明包含
        return isConcat[s.length()];
    }
}