我一开始看也想说
阿就字典树随便丢
后来看一下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什么之类的
: 看到绿色的标题
: 我就懒了
: 我好烂