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日

相关推荐

  • leetcode367-有效的完全平方数

    原题 给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。 说明: 不要使用任何内置的库函数,如  sqrt。 示例1: …

    算法 2020年1月5日
    0130
  • leetcode20-有效的括号

    原题 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序…

    算法 2019年12月11日
    0190
  • leetcode704-二分查找

    原题 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示…

    算法 2019年12月29日
    070
  • leetcode57-插入区间

    原题 给出一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 输入: …

    算法 2020年5月12日
    0270
  • leetcode219-存在重复元素II

    原题 给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k。 示例1…

    算法 2019年12月24日
    0160
  • leetcode66-加一

    原题 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外,这个整数不会以…

    算法 2019年11月14日
    0140
  • leetcode912-排序数组

    原题 给定一个整数数组 nums,将该数组升序排列。 示例 1: 输入: [5,2,3,1] 输出: [1,2,3,5] 示例 2: 输入: [5,1,1,2,0,0] 输出: […

    算法 2020年3月31日
    0340
  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合…

    算法 2019年12月18日
    0140
  • leetcode429-N叉树的层序遍历

    原题 给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。 例如,给定一个 3叉树 : 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明:…

    2020年1月20日
    0120
  • leetcode79-单词搜索

    原题 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格…

    算法 2020年4月12日
    0110

发表回复

登录后才能评论