【LeetCode】单词替换 Java 题解

作者：Albert

2022 年 7 月 08 日
本文字数：1283 字
阅读完需：约 4 分钟

题目描述

在英语中，我们有一个叫做词根(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"
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/replace-words著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是字符串处理题目，题目明确了单词的拼接规则，词根 + 其他一些词，组成新的单词。题目给出了词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。我们需要在 sentence 中找出带有词根的组成单词并替换成词根。转换成程序的就是观察词根出现的位置是不是首位置。
根据题目含义，如果继承词有许多可以形成它的词根，则用最短的词根替换它。我们对 dictionary 数组进行单词长度排序。排序我们一般使用 sort() 函数，sort() 默认是按照自然序排序，也就是字母的排序和数值升序。按照单词的长度排序，我们需要自定排序规则，可以使用 Comparator 自定义排序，compare 返回一个整数，负数表示小于，0 表示相等，正数表示大于。
dictionary 数组排序完成之后，我们在替换 sentence 中的词根，完成题目要求。具体实现代码如下，供参考。

通过代码

class Solution {    public String replaceWords(List<String> dictionary, String sentence) {        dictionary.sort(new Comparator<String>() {            @Override            public int compare(String o1, String o2) {                return o1.length() - o2.length();            }        });
        StringBuilder ans = new StringBuilder();        String[] sentenceArr = sentence.split(" ");        int n = sentenceArr.length;        for (int i = 0; i < n; i++) {            String s = sentenceArr[i];            boolean findFlag = false;            for (String d : dictionary) {                if (s.indexOf(d) == 0) {                    ans.append(d);                    findFlag = true;                    break;                }            }            if (!findFlag) {                ans.append(s);            }            if (i != n - 1) {                ans.append(" ");            }        }
        return ans.toString();    }}