做个有用网站,房产网站源码wordpress,连云港网站建设价格,最好的手机网站建设【问题描述】[中等]
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict#xff0c;判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明#xff1a;拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1#xff1a;输入: s …【问题描述】[中等]
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1输入: s leetcode, wordDict [leet, code]
输出: true
解释: 返回 true 因为 leetcode 可以被拆分成 leet code。
示例 2输入: s applepenapple, wordDict [apple, pen]
输出: true
解释: 返回 true 因为 applepenapple 可以被拆分成 apple pen apple。注意你可以重复使用字典中的单词。
示例 3输入: s catsandog, wordDict [cats, dog, sand, and, cat]
输出: false
【解答思路】
1. 动态规划
动态规划流程 第 1 步设计状态 dp[i] 表示字符串 ss 前 ii 个字符组成的字符串 s[0…i-1]s[0…i−1] 是否能被空格拆分成若干个字典中出现的单词
第 2 步状态转移方程 第 3 步考虑初始化 boolean[] dp new boolean[s.length() 1]; 第 4 步考虑输出 dp[s.length()]; 第 5 步考虑是否可以状态压缩 时间复杂度O(N^2) 空间复杂度O(n)
public class Solution {public boolean wordBreak(String s, ListString wordDict) {SetString wordDictSet new HashSet(wordDict);boolean[] dp new boolean[s.length() 1];dp[0] true;for (int i 1; i s.length(); i) {for (int j 0; j i; j) {if (dp[j] wordDictSet.contains(s.substring(j, i))) {dp[i] true;break;}}}return dp[s.length()];}
}public boolean wordBreak(String s, ListString wordDict) {if (s null || s.length() 0) {return true;}if (wordDict null || wordDict.size() 0) {return false;}boolean[] dp new boolean[s.length() 1];dp[0] true;for (int i 1; i s.length(); i) {for (String word : wordDict) {int length word.length();if (i length s.substring(i - length, i).equals(word)) {dp[i] | dp[i - length];}}}return dp[s.length()];}
2. 暴力递归到记忆优化
暴力递归(超时) 从头开始遍历s,若遍历到i形成的字符串s[0-i]在字典中wordDict则只要判断s[i1 - s.length()]是否可以被空格拆分为一个或多个在字典中出现的单词即可。以这种思想构建递归 时间复杂度O(N^2) 空间复杂度O(N)
public boolean wordBreak(String s, ListString wordDict) {// 创建字典中字符串存在的set创建的同时记录字典中最长的字符串的长度HashSetString set new HashSet();for (String str : wordDict) {set.add(str);}return getResult(s,0,set);}private boolean getResult(String s, int start, HashSetString set) {if(start s.length()){return true;}for (int i start;i s.length(); i) {if(set.contains(s.substring(start,i 1))){if(getResult(s,i1,set)){return true;}}}return false;}
memorization技术优化 考虑到每次计算getResult(s,i1,set)回带来大量重复的计算所以这里使用memorization技术存储重复计算的结果 public boolean wordBreak(String s, ListString wordDict) {HashSetString set new HashSet();for (String str : wordDict) {set.add(str);}HashMapInteger,Boolean memo new HashMapInteger,Boolean();return getResult(s,0,set,memo);}private boolean getResult(String s, int start, HashSetString set,HashMapInteger,Boolean memo) {if(start s.length()){return true;}if(memo.containsKey(start)){return memo.get(start);}for (int i start;i s.length(); i) {if(set.contains(s.substring(start,i 1))){if(getResult(s,i1,set,memo)){memo.put(start,true);return true;}}}memo.put(start,false);return false;}
遍历优化 ** 考虑到每次遍历s字符串检查是否在set中存在是每次都是从头遍历到尾这样必定回带来大量的无效遍历如果当前遍历的长度大于字段中字符串的最大长度**则一定不可能匹配成功。 public boolean wordBreak(String s, ListString wordDict) {HashSetString set new HashSet();int max Integer.MIN_VALUE;for (String str : wordDict) {max Math.max(str.length(),max);set.add(str);}// 记录map记录重复的计算的结果HashMapInteger,Boolean map new HashMap();return getResult(s,0,set,max,map);}/**** param s* param start 表示索引开始位置* param set 字段中字符串的集合* param max 每次遍历s时不可以超出max长度否则肯定为false* param map 记忆表* return*/private boolean getResult(String s, int start, HashSetString set,int max,HashMapInteger,Boolean map) {if(start s.length()){return true;}if(map.containsKey(start)){return map.get(start);}// 关键步骤 遍历的时候加上max的长度限制避免无限遍历至s结尾for (int i start; i start max i s.length(); i) {if(set.contains(s.substring(start,i 1))){if(getResult(s,i1,set,max,map)){map.put(start,true);return true;}}}map.put(start,false);return false;}
【总结】
1.动态规划流程
第 1 步设计状态 第 2 步状态转移方程 第 3 步考虑初始化 第 4 步考虑输出 第 5 步考虑是否可以状态压缩
2. 递归 耗时 memorization技术优化
3.一开始只想到递归 没有想到动态规划
参考链接https://leetcode-cn.com/problems/word-break/solution/javacong-bao-li-di-gui-dao-ji-yi-you-hua-by-ngu-6/ 参考链接https://leetcode-cn.com/problems/word-break/solution/dan-ci-chai-fen-by-leetcode-solution/ 参考链接https://leetcode-cn.com/problems/word-break/solution/java-dong-tai-gui-hua-by-kelly2018/
