leetcode648-单词替换

原题

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

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

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

示例1:

输入: dict(词典) = ["cat", "bat", "rat"] sentence(句子) = "the cattle was rattled by the battery"
输出: "the cat was rat by the bat"

注:

  1. 输入只包含小写字母。
  2. 1 <= 字典单词数 <=1000
  3. 1 <=  句中词语数 <= 1000
  4. 1 <= 词根长度 <= 100
  5. 1 <= 句中词语长度 <= 1000

解法

思想

这里的词根其实就是字符串的前缀,一开始我以为出现在哪都可以。前缀可以使用字典树搜索。

代码

class Solution {
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
        String word;
    }

    public String replaceWords(List<String> dict, String sentence) {
        StringBuilder sb = new StringBuilder();
        TrieNode root = new TrieNode();
        for(String word:dict) insertToTrie(root,word);
        String[] words = sentence.split(" ");
        for(int i = 0;i<words.length;i++){
            String prefix = hasPrefix(root,words[i]);
            if(!prefix.equals("")) words[i] = prefix;
        }
        for(int i = 0;i<words.length;i++){
            sb.append(words[i]);
            if(i!=words.length-1) sb.append(" ");
        }
        return sb.toString();
    }

    /*将前缀插入字典树*/
    public void insertToTrie(TrieNode root,String word){
        TrieNode cur = root;
        for(char i:word.toCharArray()){
            if(cur.children[i-'a']==null){
                cur.children[i-'a'] = new TrieNode();
            }
            cur = cur.children[i-'a'];
        }
        cur.word = word;
    }

    /*从字典树中获取前缀*/
    public String hasPrefix(TrieNode root,String word){
        TrieNode cur = root;
        for(char i:word.toCharArray()){
            if(cur.children[i-'a']==null){
                return "";
            }
            cur = cur.children[i-'a'];
            if(cur.word!=null){;
                return cur.word;
            }
        }
        return "";
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode648-%e5%8d%95%e8%af%8d%e6%9b%bf%e6%8d%a2/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月19日
下一篇 2020年4月20日

相关推荐

  • leetcode146-LRU缓存机制

    原题 运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。 获取数据 get(key) -…

    算法 2020年5月25日
    0100
  • leetcode152-乘积最大子数组

    原题 给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 示例 1: 输入: [2,3,-2,4] 输出:…

    算法 2020年5月18日
    0120
  • leetcode392-判断子序列

    原题 https://leetcode.cn/problems/is-subsequence/description 解法 最简单的双指针略。 对于进阶场景:如果有大量输入的 S,…

    算法 5天前
    030
  • leetcode383-赎金信

    原题 https://leetcode.cn/problems/ransom-note/ 解法 记录下字母出现次数 func canConstruct(ransomNote str…

    算法 2天前
    020
  • leetcode100-相同的树

    原题 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 …

    算法 2020年5月7日
    0180
  • leetcode105-从前序与中序遍历序列构造二叉树

    原题 根据一棵树的前序遍历与中序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inord…

    算法 2020年1月13日
    090
  • leetcode994-腐烂的橘子

    原题 在给定的网格中,每个单元格可以有以下三个值之一: 值 0 代表空单元格;值 1 代表新鲜橘子;值 2 代表腐烂的橘子。每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜…

    2020年3月4日
    0100
  • 蓝桥杯试题-大小写转换

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   输入一个字符串,将大写字符变成小写、小写变成大写,然后输出 输入格式 acbAB 输出格式 ACBab …

    算法 2020年2月29日
    060
  • 剑指offer45-把数组排成最小的数

    原题(来源Leetcode) 输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: "102" …

    算法 2020年6月11日
    0140
  • leetcode701-二叉搜索树中的插入操作

    原题 给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 注意,可能存在多种有效的插入方式,只…

    算法 2020年1月16日
    0100

发表回复

登录后才能评论