[LeetCode] #139 Word Break 解題
題型解說
這是一題難度為中等的題目
需要設計一個方法，此方法會傳入一個字串 s 和 字串 list wordDict
回傳能不能利用 wordDict 內的值組合出 s
範例:
s = "applepenapple", wordDict = ["apple", "pen"]，則回傳 true
s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]，則回傳 false
解題思路 - 遞迴暴力法
這種方法簡單來說就是從頭開始切字串，如果切到存在於 wordDict 的字串時
就把剩餘字串進行下一次遞迴，直到所有狀態都走過一次或找到解答為止
執行結果: Time Limit Exceeded
程式碼
Java
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 因為要大量查詢字串存不存在，所以轉成 HashSet 會比較有效率
Set<String> set = new HashSet<>();
for (String s2: wordDict) {
set.add(s2);
}
return set.contains(s) || find(s, set);
}
private boolean find(String s, Set<String> set) {
if (s.isEmpty() || set.contains(s)) {
return true;
}
for (int i = 1, len = s.length(); i < len; i ++) {
String sub1 = s.substring(0, i);
String sub2 = s.substring(i);
if (set.contains(sub1) && find(sub2, set)) {
return true;
}
}
return false;
}
}
解題思路 - 遞迴暴力法 + 暫存
遞迴暴力法會造成超時的原因為檢查太多次一樣的字串
既然這樣那就搭配一個 HashMap 來紀錄字串的檢查結果
如果已經存在於 HashMap 中就直接回傳，可以省下大量的時間
執行結果: 通過
程式碼
Java
class Solution {
private Map<String, Boolean> map = new HashMap<>();
public boolean wordBreak(String s, List<String> wordDict) {
// 因為要大量查詢字串存不存在，所以轉成 HashSet 會比較有效率
Set<String> set = new HashSet<>();
for (String s2: wordDict) {
set.add(s2);
}
return set.contains(s) || find(s, set);
}
private boolean find(String s, Set<String> set) {
// 如果已經存在於 HashMap 中就直接回傳
if (map.containsKey(s)) {
return map.get(s);
}
if (s.isEmpty() || set.contains(s)) {
return true;
}
for (int i = 1, len = s.length(); i < len; i ++) {
String sub1 = s.substring(0, i);
String sub2 = s.substring(i);
if (set.contains(sub1) && find(sub2, set)) {
// 儲存結果
map.put(s, true);
return true;
}
}
// 儲存結果
map.put(s, false);
return false;
}
}
解題思路 - 動態規劃(版本一)
我使用上面的解法通過後就去了解一下其他人的解法
找到了比遞迴更有效率的方法，這個方法解釋起來比較複雜
我自己也是看了一堆資料後才吸收完畢，今天嘗試用簡單的圖解分享給大家
s = "leetcode", wordDict = ["leet", "code"]
首先建立一個布林值陣列，長度為 s.length() +1
並將陣列索引 0 設為 true，這麼做的原因在於強制啟動第一次檢查
之後準備兩個迴圈
boolean[] flag = new boolean[s.length() +1];
flag[0] = true;
for (int i = 1, len = s.length(); i <= len; i++) {
for (int j = 0; j < i; j++) {
if (!flag[j]) {
continue;
}
String sub = s.substring(j, i);
if (set.contains(sub)) {
flag[i] = true;
}
}
}
初始狀態圖解如下
i = 1、j = 0
j = 0 的時候 flag[j] 是永遠成立的，所以 sub 的值會是 s.substring(0, 1) = l
但是 l 並不在 wordDict 中
i = 2、j = 0
j = 0 的時候 flag[j] 是永遠成立，故 sub 的值會是 s.substring(0, 2) = le
但是 le 並不在 wordDict 中
這邊不檢查 j = 1 的原因為 l 既然不存在於 wordDict 中
那麼就不需要取 s.substring(1, 2) = e，因為那肯定不會有解的
i = 3、j = 0
j = 0 的時候 flag[j] 是永遠成立，故 sub 的值會是 s.substring(0, 3) = lee
但是 lee 並不在 wordDict 中
i = 4、j = 0
j = 0 的時候 flag[j] 是永遠成立，故 sub 的值會是 s.substring(0, 4) = leet
這時 leet 存在於 wordDict 中，就把 flag[4] 的值更改為 true
i = 5、j = 0
j = 0 的時候 flag[j] 是永遠成立，故 sub 的值會是 s.substring(0, 5) = leetc
但是 leetc 並不在 wordDict 中
i = 5、j = 4
因為在 i = 4、j = 0 的狀況中已經確定 leet 是存在於 wordDict 中的
那麼 leet 右側的字串也需要檢查，故 sub 的值會是 s.substring(4, 5) = c
但是 c 並不在 wordDict 中
i = 6、j = 0
j = 0 的時候 flag[j] 是永遠成立，故 sub 的值會是 s.substring(0, 5) = leetco
但是 leetco 並不在 wordDict 中
i = 6、j = 4
因為在 i = 4、j = 0 的狀況中已經確定 leet 是存在於 wordDict 中的
那麼 leet 右側的字串也需要檢查，故 sub 的值會是 s.substring(4, 6) = co
但是 co 並不在 wordDict 中
i = 7、j = 0
j = 0 的時候 flag[j] 是永遠成立，故 sub 的值會是 s.substring(0, 7) = leetcod
但是 leetcod 並不在 wordDict 中
i = 7、j = 4
因為在 i = 4、j = 0 的狀況中已經確定 leet 是存在於 wordDict 中的
那麼 leet 右側的字串也需要檢查，故 sub 的值會是 s.substring(4, 7) = cod
但是 cod 並不在 wordDict 中
i = 8、j = 0
j = 0 的時候 flag[j] 是永遠成立，故 sub 的值會是 s.substring(0, 8) = leetcode
但是 leetcode 並不在 wordDict 中
i = 8、j = 4
因為在 i = 4、j = 0 的狀況中已經確定 leet 是存在於 wordDict 中的
那麼 leet 右側的字串也需要檢查，故 sub 的值會是 s.substring(4, 8) = code
這時 code 存在於 wordDict 中，就把 flag[8] 的值更改為 true
跑完所有迴圈後將陣列最後一個元素輸出就是答案了
利用標記可以省去很多不必要的比對
執行結果: 通過
程式碼
Java
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 因為要大量查詢字串存不存在，所以轉成 HashSet 會比較有效率
Set<String> set = new HashSet<>();
for (String s2: wordDict) {
set.add(s2);
}
boolean[] flag = new boolean[s.length() +1];
flag[0] = true;
for (int i = 1, len = s.length(); i <= len; i++) {
for (int j = 0; j < i; j++) {
if (!flag[j]) {
continue;
}
String sub = s.substring(j, i);
if (set.contains(sub)) {
flag[i] = true;
}
}
}
return flag[s.length()];
}
}
解題思路 - 動態規劃(版本二)
這個版本也是使用動態規劃，但不一樣的地方是第二層迴圈歷遍的是 wordDict
只取與 wordDict 中的字串一樣長度的子字串來比對
版本一能理解的話，版本二肯定也能理解
核心思想都一樣，只是方式不同而已
執行結果: 通過
程式碼
Java
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 因為要大量查詢字串存不存在，所以轉成 HashSet 會比較有效率
Set<String> set = new HashSet<>();
for (String s2: wordDict) {
set.add(s2);
}
boolean[] flag = new boolean[s.length() +1];
flag[0] = true;
for (int i = 0, len = s.length(); i < len; i++) {
if (!flag[i]) {
continue;
}
for (String word: wordDict) {
int subLen = i + word.length();
if (subLen > len) {
continue;
}
String sub = s.substring(i, subLen);
if (sub.equals(word)) {
flag[subLen] = true;
}
}
}
return flag[s.length()];
}
}