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

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

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

目 录CONTENT

文章目录

刷题分享:LeetCode648.单词替换【字典树】

Ysfun
2022-07-07 / 2 评论 / 1 点赞 / 213 阅读 / 1,002 字

题目对应LeetCode648. 单词替换

1. 题目描述

在英语中,我们有一个叫做 词根(root) 的概念,可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如,词根an,跟随着单词 other(其他),可以形成新的单词 another(另一个)。

现在,给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根,则用最短的词根替换它。

你需要输出替换之后的句子。

示例:

示例 1:

输入:dictionary = [“cat”,“bat”,“rat”], sentence = “the cattle was rattled by the battery”
输出:“the cat was rat by the bat”

示例 2:

输入:dictionary = [“a”,“b”,“c”], sentence = “aadsfasf absbs bbab cadsfafs”
输出:“a a b c”

2. 题解

2.1 字典树介绍

这是一道「字典树」的模板题,下面介绍字典树:

「字典树」数据结构一般用于判断是否具有相同前缀,因此非常适合用来解决当前题。

字典树结构:

class Trie {
  boolean isEnd;
  Trie[] children;
  
  public Trie() {
    children = new Trie[len];  // len取决于字典树包含字符种类数(例如,对于只包含小写字母的字典树len=26)
    isEnd = false;
  }
}

其一般包含两个属性:

  • isEnd:标识当前字典树节点是否对应单词的最后字符
  • children:子节点数组,数组长度取决于字符种类数,一般情况,对于只包含小写字母的字典树,子数组长度一般为26

2.2 字典树解法

字典树算法主要包括两个步骤:

  • 建树
  • 搜索
  1. 建树

建立一颗包含所有词根的字典树,代码如下

class Solution {
  // 建树
  public void build(Trie root, String str) {
    		// 字典树根节点root
        Trie cur = root;
        for (int i=0; i<str.length(); i++) {
            int idx = str.charAt(i) - 'a';
            if (cur.children[idx] == null) {
                cur.children[idx] = new Trie();
            }
            cur = cur.children[idx];
        }
        cur.isEnd = true;
    }
}

class Trie {
    Trie[] children;
    boolean isEnd;

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

下图展示了词根数组[abc, cb]建树过程:

  1. 搜索

找出一个单词的最短词根,代码如下:

public String check(String s, Trie root) {
  Trie cur = root;
  for (int i=0; i<s.length(); i++) {
    int idx = s.charAt(i) - 'a';
    if (cur.children[idx] == null) {
      // 当前字符在字典树中搜索不到,说明词根数组中没有与当前字符串匹配的词根
      return s;
    }
    cur = cur.children[idx];
    if (cur.isEnd) {
      // 搜索到词根的结尾,返回当前词根,当前词根为最短词根
      return s.substring(0, i+1);
    }
  }
  return s;
}

2.3 代码

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        Trie root = new Trie();
        for (String str : dictionary) {
            build(root, str);
        }
        StringBuilder builder = new StringBuilder();
        String[] arr = sentence.split(" ");
        for (int i=0; i<arr.length; i++) {
            String str = check(arr[i], root);
            builder.append(str);
            if (i != arr.length - 1) {
                builder.append(" ");
            }
        }
        return builder.toString();
    }

    public String check(String s, Trie root) {
        Trie cur = root;
        for (int i=0; i<s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if (cur.children[idx] == null) {
                return s;
            }
            cur = cur.children[idx];
            if (cur.isEnd) {
                return s.substring(0, i+1);
            }
        }
        return s;
    }

    public void build(Trie root, String str) {
        Trie cur = root;
        for (int i=0; i<str.length(); i++) {
            int idx = str.charAt(i) - 'a';
            if (cur.children[idx] == null) {
                cur.children[idx] = new Trie();
            }
            cur = cur.children[idx];
        }
        cur.isEnd = true;
    }
}

class Trie {
    Trie[] children;
    boolean isEnd;

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

复杂度分析

  • 时间复杂度:O(d + s)。其中 d 为dictionary的字符数,s 是sentence的字符数。构建字典树时间复杂度为O(d),每个单词搜索前缀均为线性时间复杂度。
  • 空间复杂度:O(d),搜索树的复杂度,即为dictionary的字符数。

运行结果:

1

评论区