Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間1年前 (2024/12/02 22:48)推噓2(2推 0噓 7→)

我一開始看也想說阿就字典樹隨便丟後來看一下easy 喔應該掃一遍就沒了ㄅ class Solution { public: int isPrefixOfWord(string s, string w) { int n = s.length(), m = w.length(); int cnt = 1; for(int i = 0, check = 1; i < n; ){ if(!check){ while(i < n and s[i] != ' ') i++; check = true; i++; cnt++; } for(int j = 0; j < m and i < n; j++, i++){ if(s[i] != w[j]){ check = false; break; } if(j == m-1) return cnt; } } return -1; } }; 寫完還是覺得字典樹比較簡單又寫了一遍== class trie{ public: vector<trie*> ch; int idx; trie(): ch(vector<trie*>(26, nullptr)), idx(0) {}; }; class Solution { public: int isPrefixOfWord(string s, string w) { int idx = 1; trie* root = new trie(); trie* cur = root; for(char& c: s){ if(c == ' ') { cur = root; idx++; } else{ if(cur->ch[c-'a'] == nullptr){ cur->ch[c-'a'] = new trie(); } cur = cur->ch[c-'a']; if(!cur->idx) cur->idx = idx; } } for(char& c: w){ if(!root) return -1; root = root->ch[c-'a']; } if(!root) return -1; return root->idx; } }; ※ 引述《DJYOMIYAHINA (通通打死)》之銘言： : 想說要用trie什麼之類的 : 看到綠色的標題 : 我就懶了 : 我好爛 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.51.137.241 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1733150939.A.DA1.html

→

sixB

12/02 22:49, 1年前 , 1^F

12/02 22:49, 1^F

推

oin1104

12/02 22:54, 1年前 , 2^F

12/02 22:54, 2^F

→

oin1104

12/02 22:54, 1年前 , 3^F

12/02 22:54, 3^F