題目連結

題型解說

這是一題難度為中等的題目

需要設計一個方法，此方法會傳入一個字串 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()];
    }
}