Re: [閒聊] 每日leetcode已回收

看板Marginalman作者sustainer123 (caster )時間1年前 (2024/06/07 11:28)推噓5(5推 0噓 3→)

留言8則, 5人參與討論串328/1550 (看更多)

※ 引述《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

06/07 11:29, 1年前 , 1^F

06/07 11:29, 1^F

推

JIWP

06/07 11:30, 1年前 , 2^F

06/07 11:30, 2^F

→

sustainer123

06/07 11:32, 1年前 , 3^F

06/07 11:32, 3^F