Re: [閒聊] 每日leetcode

[sustainer123 (caster )]

※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: 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;
:     }
: }
: -----------------------------------------

思路差不多 不過我原本多了對字根長度的排序

後來想想確實不用排

因為遇到短的會先跳出

雖然排序與否不太影響速度 姆咪


Python Code:
class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        class TrieNode:
            def __init__(self):
                self.children = {}
                self.is_word = False

        class Trie:
            def __init__(self):
                self.root = TrieNode()

            def insert(self,word:str):
                node = self.root

                for c in word:
                    if c not in node.children:
                        node.children[c] = TrieNode()
                    node = node.children[c]
                node.is_word = True

            def Startwith(self,prefix:str):
                node = self.root
                s = ""
                for c in prefix:
                    if c not in node.children:
                        return None
                    s = s+c
                    node = node.children[c]
                    if node.is_word:
                        return s
                return s


        record = Trie()
        words = sentence.split()


        for w in dictionary:
            record.insert(w)

        for i in range(len(words)):
            root = record.Startwith(words[i])

            if root:
                words[i] = root

        return " ".join(words)








--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1717730925.A.151.html
推 SecondRun: 大師
推 JIWP: 你們都用字典樹喔
→ sustainer123: 找前綴用字典樹最直觀ㄅ 只是有點難刻
推 JIWP: 我懶得刻，用hash table
→ sustainer123: 我順便複習 不然會忘記怎麼刻
推 JIWP: 也是等下來練習一下好了
推 wu10200512: 別卷了
→ DJYOSHITAKA: 別捲了 肥肥不會trie