侧边栏壁纸
博主头像
Ysfun博主等级

一名热爱技术、喜欢折腾的小小程序猿

  • 累计撰写 42 篇文章
  • 累计创建 14 个标签
  • 累计收到 21 条评论

目 录CONTENT

文章目录

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

Ysfun
2022-06-17 / 0 评论 / 0 点赞 / 64 阅读 / 571 字

题目对应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];
    }
}

0

评论区