我一開始看也想說
阿就字典樹隨便丟
後來看一下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什麼之類的
: 看到綠色的標題
: 我就懶了
: 我好爛