LeetCode-139-单词拆分 LeetCode-139-单词拆分

单词拆分

题目描述：给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

示例说明请见LeetCode官网。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：穷举法

使用穷举+递归的方式求解，效率较低，具体处理过程如下：

如果当前字符串为null或者为空字符串，则默认可以由字符串字典切分，直接返回true；

否则，遍历字符串字典中的字符串：

如果某个字符串刚好和当前字符串相等并且长度一致，则直接返回true；

如果某个字符串和当前字符串相等但是长度不一致，递归判断后面的字符串并返回判断的结果。

最后，返回最终判断的结果。

解法二：动态规划

首先，初始化字符串字典到哈希表wordDictSet中，便于快速查找；

然后初始化一个dp数组，数组的长度为原始字符串的长度加1，并初始化数组的第一个元素为true；

【LeetCode-139-单词拆分】然后遍历字符串，判断从0到i的字符串是否可以由字符串字典切分而成：

判断逻辑是从0到j的字符串可以由字符串字典切分（这个根据前面的计算得到）并且从j到i 的字符串在字符串字典中。

最终，返回dp数组的最后一个元素即为最终结果。

import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class LeetCode_139 { private static boolean flag = false; /** * 穷举法 * * @param s * @param wordDict * @return */ public static boolean wordBreak(String s, List wordDict) { if (s == null || s.length() == 0) { return true; }for (String word : wordDict) { if (flag) { return flag; } if (s.startsWith(word)) { if (s.length() == word.length()) { // 如果当前字符与字符串字典中的某个字符串匹配并且长度相同，则说明当前字符串可以由字符串字典切分成，返回true return true; } // 如果当前字符串由某个字符串字典中的字符串切分后，还有待判断的字符，则递归判断后面的字符串 flag = wordBreak(s.substring(word.length()), wordDict); } } return flag; }/** * 动态规划 * * @param s * @param wordDict * @return */ public static boolean wordBreak2(String s, List wordDict) { // 初始化字符串字典到哈希表中，便于快速查找 Set wordDictSet = new HashSet<>(wordDict); boolean[] dp = new boolean[s.length() + 1]; // 默认空字符串可以由字符串字典切分而成，初始置为true dp[0] = true; // 判断从0到i的字符串是否可以由字符串字典切分而成 for (int i = 1; i <= s.length(); i++) { for (int j = 0; j < i; j++) { // 判断逻辑是从0到j的字符串可以由字符串字典切分（这个根据前面的计算得到）并且从j到i 的字符串在字符串字典中 if (dp[j] && wordDictSet.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[s.length()]; }public static void main(String[] args) { String s = "applepenapple"; List wordDict = new ArrayList<>(); wordDict.add("apple"); wordDict.add("pen"); System.out.println(wordBreak(s, wordDict)); System.out.println(wordBreak2(s, wordDict)); } }