【Hot100】LeetCode—139. 单词拆分

• 原题链接：139. 单词拆分

1- 思路

题目识别

• 识别1 ：字符串 和一个 字符串数组 判断
• 识别2：判断字符串能不能由字符串数组拼接形成，返回 true 或 false

完全背包-动规五部曲

拆分时可以重复使用字典中的单词，可以看为是一个完全背包的问题

思路：①布尔类型的 dp 数组、②定 i（从1开始） 移动 j（从 0 开始）；通过 substring(j,i) 区间内的字符串，判断是否在 wordDict 中，如果在则置 dp[i] 为 true

2- 实现

⭐单词拆分——题解思路

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 1. 定义 dp 数组
        // 含义 dp[i] 代表以 i 结尾的字符串能否由 数组内容组成
        int len = s.length();
        boolean[] dp = new boolean[len+1];

        // 2.递推公式
        // substring(j,i) 有的话 dp[i] = true;

        // 3. 初始化
        dp[0] = true;

        for(int i = 1 ; i <= len;i++){
            for(int j = 0 ; j < i ; j++){
                if(wordDict.contains(s.substring(j,i)) && dp[j]){
                    dp[i] = true;
                }
            }
        }
        
        return dp[len];
    }
}

3- ACM 实现

public class wordSplit {

    public static boolean splitWord(String s,List<String> wordDict){
        // 1. 定义 dp 数组
        int len = s.length();
        boolean[] dp = new boolean[len+1];

        // 2.递推公式
        // if(dp[j] && s.substring(j,i))

        // 3.初始化
        dp[0] = true;
        for(int i = 1 ; i <= len;i++){
            for(int j = 0 ; j < i ;j++){
                if(dp[j] && wordDict.contains(s.substring(j,i))){
                    dp[i] = true;
                }
            }
        }
        return dp[len];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入字符串");
        String input = sc.nextLine();
        System.out.println("输入字符数组长度");
        int n = sc.nextInt();
        List<String> list = new ArrayList<>();
        String konge = sc.nextLine();
        for(int i  = 0 ; i < n;i++){
            String str = sc.nextLine();
            list.add(str);
        }

        System.out.println("结果是"+splitWord(input,list));
    }
}