LeetCode-139-单词拆分

大家好，欢迎来到IT知识分享网。

单词拆分

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

说明：

• 拆分时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/word-break/

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：穷举法

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

• 如果当前字符串为null或者为空字符串，则默认可以由字符串字典切分，直接返回true；
• 否则，遍历字符串字典中的字符串：如果某个字符串刚好和当前字符串相等并且长度一致，则直接返回true；如果某个字符串和当前字符串相等但是长度不一致，递归判断后面的字符串并返回判断的结果。
• 最后，返回最终判断的结果。

解法二：动态规划

• 首先，初始化字符串字典到哈希表wordDictSet中，便于快速查找；
• 然后初始化一个dp数组，数组的长度为原始字符串的长度加1，并初始化数组的第一个元素为true；
• 然后遍历字符串，判断从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<String> 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<String> wordDict) { // 初始化字符串字典到哈希表中，便于快速查找 Set<String> 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<String> wordDict = new ArrayList<>(); wordDict.add("apple"); wordDict.add("pen"); System.out.println(wordBreak(s, wordDict)); System.out.println(wordBreak2(s, wordDict)); } }

【每日寄语】 要相信机会总是会有的，不要和自己较劲，要顺势，像太极推手一样，顺势而为，要学会利用周边资源。