Why I'm getting WA??↵
<br>↵
**Please check out->[Leetcode problem Submission link**<br>↵
Problem link [problem](https://leetcode.com/problems/extra-characters-in-a-string/submissions/1399962903/?envType=daily-question&envId=2024-09-23)description/?envType=daily-question&envId=2024-09-23)↵
<br>↵
**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));↵
}↵
};↵
~~~~~↵
<br>↵
**Failed test case :** <br>↵
String: "tpqojlnhenbzmqkqnxohmzakm"<br>↵
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"]<br>↵
**My output:** 4<br>↵
**Expected output:** 1<br>↵
↵
↵
↵
**Please check out
Problem link [problem](https://leetcode.com/problems/extra-characters-in-a-string/
<br>↵
**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));↵
}↵
};↵
~~~~~↵
<br>↵
**Failed test case :** <br>↵
String: "tpqojlnhenbzmqkqnxohmzakm"<br>↵
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"]<br>↵
**My output:** 4<br>↵
**Expected output:** 1<br>↵
↵
↵
↵
