題目

在英語(yǔ)中，我們有一個(gè)叫做 詞根(root) 的概念，可以詞根后面添加其他一些詞組成另一個(gè)較長(zhǎng)的單詞——我們稱這個(gè)詞為 繼承詞(successor)。例如，詞根an，跟隨著單詞 other(其他)，可以形成新的單詞 another(另一個(gè))。

現(xiàn)在，給定一個(gè)由許多詞根組成的詞典 dictionary 和一個(gè)用空格分隔單詞形成的句子 sentence。你需要將句子中的所有繼承詞用詞根替換掉。如果繼承詞有許多可以形成它的詞根，則用最短的詞根替換它。

你需要輸出替換之后的句子。

示例

輸入：dictionary = [“cat”,“bat”,“rat”], sentence = “the cattle was rattled by the battery”
輸出：“the cat was rat by the bat”

輸入：dictionary = [“a”,“b”,“c”], sentence = “aadsfasf absbs bbab cadsfafs”
輸出：“a a b c”

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/replace-words
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

方法1：哈希表模擬

Java實(shí)現(xiàn)

class Solution {public String replaceWords(List<String> dictionary, String sentence) {Set<String> set = new HashSet<>();for (String d : dictionary) set.add(d);String[] strs = sentence.split(" ");for (int i = 0; i < strs.length; i++) {String str = strs[i];for (int j = 0; j < str.length(); j++) {if (set.contains(str.substring(0, j + 1))) {strs[i] = str.substring(0, j + 1);break;}}}return String.join(" ", strs);} }

總結(jié)

以上是生活随笔為你收集整理的力扣 648. 单词替换的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。