Please read the new rule regarding the restriction on the use of AI tools. ×

-200's blog

By -200, history, 6 hours ago, In English

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

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it