【問題描述】[中等]
給定一個非空字符串 s 和一個包含非空單詞列表的字典 wordDict，判定 s 是否可以被空格拆分為一個或多個在字典中出現(xiàn)的單詞。說明：拆分時可以重復(fù)使用字典中的單詞。
你可以假設(shè)字典中沒有重復(fù)的單詞。
示例 1：輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因為 "leetcode" 可以被拆分成 "leet code"。
示例 2：輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因為 "applepenapple" 可以被拆分成 "apple pen apple"。注意你可以重復(fù)使用字典中的單詞。
示例 3：輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false
【解答思路】
1. 動態(tài)規(guī)劃
動態(tài)規(guī)劃流程
第 1 步：設(shè)計狀態(tài)
dp[i] 表示字符串 ss 前 ii 個字符組成的字符串 s[0…i-1]s[0…i?1] 是否能被空格拆分成若干個字典中出現(xiàn)的單詞
第 2 步：狀態(tài)轉(zhuǎn)移方程
第 3 步：考慮初始化
boolean[] dp = new boolean[s.length() + 1];
第 4 步：考慮輸出
dp[s.length()];
第 5 步：考慮是否可以狀態(tài)壓縮
時間復(fù)雜度：O(N^2) 空間復(fù)雜度：O(n)
public class Solution {public boolean wordBreak(String s
, List
<String> wordDict
) {Set
<String> 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
, List
<String> 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. 暴力遞歸到記憶優(yōu)化
暴力遞歸(超時)
從頭開始遍歷s,若遍歷到i形成的字符串s[0-i]在字典中wordDict，則只要判斷s[i+1 - s.length()]是否可以被空格拆分為一個或多個在字典中出現(xiàn)的單詞即可。以這種思想構(gòu)建遞歸
時間復(fù)雜度：O(N^2) 空間復(fù)雜度：O(N)
public boolean wordBreak(String s
, List
<String> wordDict
) {HashSet
<String> set
= new HashSet<>();for (String str
: wordDict
) {set
.add(str
);}return getResult(s
,0,set
);}private boolean getResult(String s
, int start
, HashSet
<String> 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
,i
+1,set
)){return true;}}}return false;}
memorization技術(shù)優(yōu)化
考慮到每次計算getResult(s,i+1,set)回帶來大量重復(fù)的計算，所以這里使用memorization技術(shù)存儲重復(fù)計算的結(jié)果
public boolean wordBreak(String s
, List
<String> wordDict
) {HashSet
<String> set
= new HashSet<>();for (String str
: wordDict
) {set
.add(str
);}HashMap
<Integer,Boolean> memo
= new HashMap<Integer,Boolean>();return getResult(s
,0,set
,memo
);}private boolean getResult(String s
, int start
, HashSet
<String> set
,HashMap
<Integer,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
,i
+1,set
,memo
)){memo
.put(start
,true);return true;}}}memo
.put(start
,false);return false;}
遍歷優(yōu)化 **
考慮到每次遍歷s字符串，檢查是否在set中存在是，每次都是從頭遍歷到尾，這樣必定回帶來大量的無效遍歷，如果當前遍歷的長度大于字段中字符串的最大長度**，則一定不可能匹配成功。
public boolean wordBreak(String s
, List
<String> wordDict
) {HashSet
<String> set
= new HashSet<>();int max
= Integer
.MIN_VALUE
;for (String str
: wordDict
) {max
= Math
.max(str
.length(),max
);set
.add(str
);}HashMap
<Integer,Boolean> map
= new HashMap<>();return getResult(s
,0,set
,max
,map
);}private boolean getResult(String s
, int start
, HashSet
<String> set
,int max
,HashMap
<Integer,Boolean> map
) {if(start
== s
.length()){return true;}if(map
.containsKey(start
)){return map
.get(start
);}for (int i
= start
; i
< start
+ max
&& i
< s
.length(); i
++) {if(set
.contains(s
.substring(start
,i
+ 1))){if(getResult(s
,i
+1,set
,max
,map
)){map
.put(start
,true);return true;}}}map
.put(start
,false);return false;}
【總結(jié)】
1.動態(tài)規(guī)劃流程
第 1 步：設(shè)計狀態(tài)
第 2 步：狀態(tài)轉(zhuǎn)移方程
第 3 步：考慮初始化
第 4 步：考慮輸出
第 5 步：考慮是否可以狀態(tài)壓縮
2. 遞歸 耗時 memorization技術(shù)優(yōu)化
3.一開始只想到遞歸 沒有想到動態(tài)規(guī)劃
參考鏈接：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/
總結(jié)
以上是生活随笔為你收集整理的[Leedcode][JAVA][第139题][单词拆分][递归][记忆优化][动态规划]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
