刷题分享：LeetCode139.单词拆分【字典树，动态规划】

题目对应LeetCode139. 单词拆分

1. 题目描述

给你一个字符串 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

2. 代码分析

【动态规划】+【字典树】

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Trie root = build(wordDict);
        int n = s.length();
        // 动态规划，转移方程：dp[i] = dp[i-k] && (s[i-k,i] in wordDict)
        boolean[] dp = new boolean[n];
        for (int i=0; i<n; i++) {
            List<Integer> list = check(s, root, i);
            for (int idx : list) {
                // 可能有多个位置匹配，只要存在一个k满足 dp[i-k] && (s[i-k,i] in wordDict) == true，则dp[i]为true
                if (idx==0 || dp[idx-1]) {
                    dp[i] = true;
                }
            }
        }
        return dp[n-1];
    }

    /**
     * 判断是否满足最右匹配
     */
    public List<Integer> check(String s, Trie root, int lastIndex) {
        Trie node = root;
        List<Integer> list = new ArrayList<>();
        while (lastIndex >= 0) {
            int index = s.charAt(lastIndex) - 'a';
            if (node.children[index] == null) {
                break;
            }
            node = node.children[index];
            if (node.isEnd) {
                // 如果满足最右匹配，且到达单词末尾，将该Index加入List
                list.add(lastIndex);
            }
            lastIndex--;
        }
        return list;
    }

    /**
     * 建立字典树，建立字典树的基本套路
     */
    public Trie build(List<String> wordDict) {
        Trie root = new Trie();
        for (String s : wordDict) {
            Trie node = root;
            // 这里需要注意，单词尾部向头部遍历，方便check时的最右匹配
            for (int i=s.length()-1; i>=0; i--) {
                int idx = s.charAt(i)-'a';
                if (node.children[idx] == null) {
                    node.children[idx] = new Trie();
                }
                node = node.children[idx];
            }
            node.isEnd = true;
        }
        return root;
    }
}

/**
 * 字典树的典型结构
 */
class Trie{
    Trie[] children;
    boolean isEnd;

    public Trie() {
        children = new Trie[26];
    }
}