Re: [閒聊] 每日leetcode已回收
https://leetcode.com/problems/replace-words/description
648. Replace Words
給你一個字串列表dictionary和一個字串sentence，sentence裡面有很多單字，這些單字
被空白分割，有些單字是從其他單字的字首延伸的例如：helpful = help+ful 若
sentence裡面的單字字首存在於dictionary我們可以把原單字替換成較短的字首，若
存在多個字首則取最短，求出替換完的句子長什麼樣子。
Example 1:
Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled
by the battery"
Output: "the cat was rat by the bat"
思路:
1.前面忘了中間忘了憑印象手刻一個字典樹，先把所有字根加入字典樹。
2.接下來把sentence依照空白切成單字，如果這個單字在字典樹裡面就加入第一個找到的
字根，找不到就返回原單字。
3.把結果集串起來用空白分割。
java code
-----------------------------------------
class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
Trie root = new Trie();
for (String word : dictionary) {
Trie curr = root;
for (char ch : word.toCharArray()) {
if (curr.next[ch - 'a'] == null) {
curr.next[ch - 'a'] = new Trie();
}
curr = curr.next[ch - 'a'];
}
curr.isEnd = true;
}
StringBuilder sb = new StringBuilder();
for (String word : sentence.split(" ")) {
boolean find = false;
StringBuilder currWord = new StringBuilder();
Trie curr = root;
for (char ch : word.toCharArray()) {
if (curr.isEnd) {
find = true;
break;
}
if (curr.next[ch - 'a'] == null) {
break;
}
currWord.append(ch);
curr = curr.next[ch - 'a'];
}
if (find) {
sb.append(currWord).append(" ");
} else {
sb.append(word).append(" ");
}
}
return sb.deleteCharAt(sb.length() - 1).toString();
}
}
class Trie {
Trie[] next;
boolean isEnd;
public Trie() {
this.next = new Trie[26];
this.isEnd = false;
}
}
-----------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1717725126.A.2A4.html
推
06/07 09:56,
1年前
, 1F
06/07 09:56, 1F
推
06/07 09:58,
1年前
, 2F
06/07 09:58, 2F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 327 之 1550 篇)：