Original link: https://wlnxing.com/archives/69.html
topic
648 word replacements
In English, we have a concept called a词根, after which some other words can be added to form another longer word – we call this继承词successor. For example, the root an , followed by the word other , can form the new word another .
Now, given a dictionary consisting of many roots and a sentence formed by separating words with spaces. You need to replace all inherited words in the sentence with root words. If the inherited word has many roots that can form it, replace it with the shortest root .
You need to output the sentence after the replacement.
io
Example 1:
输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"输出："the cat was rat by the bat"Example 2:
输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"输出："aabc"hint
- 1 <= dictionary.length <= 1000
- 1 <= dictionary[i].length <= 100
- dictionary[i] consists of lowercase letters only.
- 1 <= sentence.length <= 10^6
- sentence consists of lowercase letters and spaces only.
- The total number of words in the sentence is in the range [1, 1000].
- The length of each word in the sentence is in the range [1, 1000].
- The words in the sentence are separated by a space.
- sentence has no leading or trailing spaces.
code
/** * @param {string[]} dictionary * @param {string} sentence * @return {string} */ // dictionary = ["cat","bat","rat"] sentence = "the cattle was rattled by the battery" var replaceWords = function(dictionary, sentence) { // 根据dictionary建立字典树const tree=new Map(); for(const word of dictionary) { let cur=tree for(const letter of word){ if(!cur.has(letter)){ cur.set(letter,new Map()) } cur=cur.get(letter) } cur.set('@',new Map()) } const words=sentence.split(" ") words.forEach((word,i)=>{ let cur=tree let res_t='' for(let letter of word){ // 词根已经到末尾了结束循环if(cur.has('@')){ break } if(cur.has(letter)){ // 继续匹配单词res_t+=letter cur=cur.get(letter) } else { // 走到这了说明没有词根匹配上res_t=word break } } words[i]=res_t }) return words.join(' ') }; replaceWords(["cat","bat","rat"],"the cattle was rattled by the battery");
This article is reprinted from: https://wlnxing.com/archives/69.html
This site is for inclusion only, and the copyright belongs to the original author.