Why I'm getting WA??
Please check out
Problem link problem
My submission code
Your code here...
struct Node{
Node *links[26];
bool flag = false;
};
class trie{
private:
Node *root;
public:
trie(){
root = new Node();
}
void insert(string &word){
int n=word.size();
Node *temp = root;
for(int i=0;i<n;i++){
if(temp->links[word[i]-'a']==NULL) temp->links[word[i]-'a']=new Node();
temp = temp->links[word[i]-'a'];
}
temp->flag=true;
}
int help(string &s){
int n=s.size();
Node* temp = root;
int cnt=0,i=0,tp=0;
while(i<n){
if(temp->links[s[i]-'a']){
temp=temp->links[s[i]-'a'];
tp++,i++;
if(temp->flag) cnt+=tp,tp=0;
}
else{
if(root->links[s[i]-'a']) temp=root,tp=0;
else i++,tp=0,temp=root;
}
// debug(tp);
}
// debug(cnt);
return (n-cnt);
}
};
class Solution {
public:
int minExtraChar(string s, vector<string>& dict) {
trie tri;
for(auto i : dict) tri.insert(i);
return (tri.help(s));
}
};
Failed test case :
String: "tpqojlnhenbzmqkqnxohmzakm"
Dictionary:["enbzm","yy","xqnjw","cxwgv","q","ras","ezc","nt","eq","j","chfw","v","ebh","tvwk","we","xhk","bumlw","czgy","njrml","pl","cxg","ztg","mnvi","k","hslr","fwhrj","h","yqro","vpxyf","bps","nhuv","w","m","ln","nxoh","skiun","qnqc","wtrwp","hl","ydbv","cv","a","tpqoj","umrj","nq","xadnx","emwv","dmuuw"]
My output: 4
Expected output: 1
Auto comment: topic has been updated by -200 (previous revision, new revision, compare).
Seems like you do greedy matching. You should try to do dp. Let $$$dp_i$$$ be the minimum number of unmatched characters from the first $$$i$$$ characters in your string. The transitions can be computed relatively easily and time complexity is fine because limits are small.