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

题目对应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 字典树解法

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

建树
搜索

建树

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

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]建树过程：

搜索

找出一个单词的最短词根，代码如下：

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的字符数。

运行结果：

目录CONTENT