【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));}
}

---