【Leetcode】140. Word Break II

題目位址：

https://leetcode.com/problems/word-break-ii/

給定一個字元串 s s s，再給定若幹單詞的清單 A A A，求所有清單中單詞拼起來成為 s s s的所有方式。以清單的形式傳回，單詞之間以空格分開。例如，

s = "catsanddog"

，單詞清單為

["cat", "cats", "and", "sand", "dog"]

，那麼要傳回的就是

["cats and dog", "cat sand dog"]

，單詞間以空格隔開。

法1：DFS。可以枚舉第一次分割出來的子串，如果這個子串存在于清單裡，并且後面能分割成清單裡單詞的組合，那麼就将其分割出來，然後從這個子串後面一位繼續DFS。為了能迅速判斷後面是否能分割成清單裡單詞的組合，我們可以預處理一個boolean數組 f [ i ] f[i] f[i]表示 s s s的後 i i i個字元是否能被組合出來。同時為了迅速判斷一個字元串是否存在于清單，我們可以用Trie優化。DFS的同時記錄路徑即可。代碼如下：

import java.util.ArrayList;
import java.util.List;

public class Solution {
    // 把Trie寫出來
    class Trie {
        class Node {
            Node[] nexts;
            boolean isWord;
            
            public Node() {
                nexts = new Node[26];
            }
        }
        
        Node root;
        
        public Trie() {
            root = new Node();
        }
        
        public void insert(String s) {
            Node cur = root;
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (cur.nexts[ch - 'a'] == null) {
                    cur.nexts[ch - 'a'] = new Node();
                }
                cur = cur.nexts[ch - 'a'];
            }
            
            cur.isWord = true;
        }
        
        public boolean contains(String s) {
            Node cur = root;
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (cur.nexts[ch - 'a'] == null) {
                    return false;
                }
                cur = cur.nexts[ch - 'a'];
            }
            
            return cur.isWord;
        }
    }
    
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> res = new ArrayList<>();
        
        Trie trie = new Trie();
        // 将所有單詞加入trie，并且求一下清單裡最長單詞長度和最短單詞長度
        int minl = Integer.MAX_VALUE, maxl = 0;
        for (String word : wordDict) {
            trie.insert(word);
            minl = Math.min(minl, word.length());
            maxl = Math.max(maxl, word.length());
        }
        
        // dp[i]表示s的後i個字元組成的字元串是否能被組合出來
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        // 計算s的後i個字元的字元串是否能被組合出來
        for (int i = 1; i <= s.length(); i++) {
        	// s的後i個字元的字元串是否能被組合出來當且僅當，
        	// s的後j個字元能組合出來，并且s的後i個字元去掉後j個字元的子串仍然在trie裡
            for (int j = 0; j <= i; j++) {
            	// s的後i個字元去掉後j個字元的子串如果長度不符合，就不用判斷了
                if (i - j >= minl && i - j <= maxl) {
                    dp[i] = dp[j] && trie.contains(s.substring(s.length() - i, s.length() - j));
                    // 發現能，就及時退出
                    if (dp[i]) {
                        break;
                    }
                }
            }
        }
        
        dfs(new StringBuilder(), s, 0, dp, trie, res, minl, maxl);
        return res;
    }
    
    private void dfs(StringBuilder sb, String s, int pos, boolean[] dp, Trie trie, List<String> res, int minl, int maxl) {
    	// 如果切割完畢了，就将得到的sb去掉最後一個空格後加入res
        if (pos == s.length()) {
            res.add(sb.substring(0, sb.length() - 1));
            return;
        }
        
        // 枚舉切出s[pos, i]這個子串
        for (int i = pos; i < s.length(); i++) {
        	// 如果這個子串長度符合條件，則進入下一層邏輯
            if (i - pos + 1 >= minl && i - pos + 1 <= maxl) {
            	// 取出切出來的子串
                String cur = s.substring(pos, i + 1);
                // 如果這個子串存在于trie，并且後面的子串能被切割出來，那就切
                if (trie.contains(cur) && dp[s.length() - i - 1]) {
                	// 将該子串加入sb，後面加上空格
                    sb.append(cur).append(' ');
                    // 從i + 1的位置繼續搜尋
                    dfs(sb, s, i + 1, dp, trie, res, minl, maxl);
                    // 回溯的時候恢複現場
                    sb.setLength(sb.length() - cur.length() - 1);
                }
            }
        }
    }
}
           

時間複雜度是指數級别的，空間複雜度 O ( s + l n ) O(s+ln) O(s+ln)， s s s為字元串長度， l l l是清單裡最長單詞長度， n n n為單詞個數。

法2：DFS + 字元串哈希。這裡由于要頻繁判斷 s s s的某個子串是否在wordDict裡，最好的辦法還是采用字元串哈希。同樣可以用動态規劃預處理一下，我們這裡可以開個boolean數組 f f f，使得 f [ i ] f[i] f[i]是 s s s的長 i i i的字首是否存在切割方案。那麼 f [ i ] = ⋁ 0 ≤ j ≤ i − 1 ( f [ j ] ∧ s [ j : i − 1 ] ∈ A ) f[i]=\bigvee_{0\le j\le i-1} (f[j]\land s[j:i-1]\in A) f[i]=0≤j≤i−1⋁​(f[j]∧s[j:i−1]∈A)預處理出 f f f之後DFS可以有剪枝的效果。代碼如下：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        long P = 131;
        // 預處理一下s的字首哈希數組，和P的各個幂次
        long[] hashS = new long[s.length() + 1], pow = new long[s.length() + 1];
        pow[0] = 1;
        for (int i = 0; i < s.length(); i++) {
            hashS[i + 1] = hashS[i] * P + s.charAt(i);
            pow[i + 1] = pow[i] * P;
        }
        
        // 将wordDict裡所有字元串的哈希值存進一個哈希表裡
        Set<Long> set = new HashSet<>();
        for (String word : wordDict) {
            long hash = 0;
            for (int i = 0; i < word.length(); i++) {
                hash = hash * P + word.charAt(i);
            }
            
            set.add(hash);
        }
        
        // 預處理一下s的各個長度的字首是否存在切割方案
        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 (set.contains(hashS[i] - hashS[j] * pow[i - j])) {
                    dp[i] |= dp[j];
                   	// 一旦算出存在方案，就可以退出循環了
                    if (dp[i]) {
                        break;
                    }
                }
            }
        }
        
        List<String> res = new ArrayList<>();
        if (!dp[s.length()]) {
            return res;
        }
        
        dfs(s.length() - 1, s, new ArrayList<>(), set, dp, hashS, pow, res);
        return res;
    }
    
    private void dfs(int pos, String s, List<String> list, Set<Long> set, boolean[] dp, long[] hashS, long[] pow, List<String> res) {
        if (pos == -1) {
            StringBuilder sb = new StringBuilder();
            for (int i = list.size() - 1; i >= 0; i--) {
                sb.append(list.get(i)).append(' ');
            }
            
            res.add(sb.substring(0, sb.length() - 1));
            return;
        }
    
        for (int i = pos; i >= 0; i--) {
            if (dp[i] && set.contains(hashS[pos + 1] - hashS[i] * pow[pos - i + 1])) {
                list.add(s.substring(i, pos + 1));
                dfs(i - 1, s, list, set, dp, hashS, pow, res);
                list.remove(list.size() - 1);
            }
        }
    }
}
           

時空複雜度一樣。