Diiferent answers (SUBMIT vs CUSTOM INPUT)


#1

Diiferent answers when submitting versus when I run as custom input. Very hard to debug where I am going wrong.

Here is my code. Can someone please look at it and tell me where I am going wrong?

struct TrieNode
{
     struct TrieNode *children[26];
     int isEndOfWord;
     TrieNode () {
         isEndOfWord = 1;
         for (int i = 0; i < 26; i++)
            children[i] = NULL;
     }
};

void insert (TrieNode* root, string word) {
    TrieNode* curr = root;
    
    for (int i=0; i<word.length(); i++) {
        if (curr->children[word[i]-'a']==NULL) {
            curr->children[word[i]-'a'] = new TrieNode ();
        }
        curr = curr->children[word[i]-'a'];
    }
    
    curr->isEndOfWord = 1;
}

int search (TrieNode* root, string word) {
    TrieNode* curr = root;
    
    if (curr==NULL)
        return 0;
       
    for (int i=0; i<word.length(); i++) {
        if (curr->children[word[i]-'a']==NULL) {
            return 0;
        }
     
        curr = curr->children[word[i]-'a'];
    }
    
    return curr->isEndOfWord;
}

bool cmp (const pair <int, int> a, const pair <int, int> b) {
        return a.first>b.first;
}

vector<int> Solution::solve(string A, vector<string> &B) {
    stringstream ss(A);
    vector<string> goodWords;
    string item;
    
    while (std::getline(ss, item, '_'))
       goodWords.push_back(item);
    
    TrieNode* root = new TrieNode ();
    for (int i=0; i<goodWords.size(); i++)
        insert(root, goodWords[i]);
        
    vector <pair <int, int> > sen;
    for (int i=0; i<B.size(); i++) {
        stringstream ss(B[i]);
        vector <string> tokens;
        int count=0;
        
        while (std::getline(ss, item, '_'))
            tokens.push_back(item); 
            
        for (int j=0; j<tokens.size(); j++) { //cout<<tokens[j];
            
            count+=search(root, tokens[j]);
        }
        
        sen.push_back(make_pair(count, i)); //cout<<count<<" ";
    }
     
    stable_sort(sen.begin(), sen.end(), cmp);
    vector <int> ans;
    
    for (int i=0; i<sen.size(); i++) {
        ans.push_back(sen[i].second);
    }
    
    return ans;
}

#3

yeah, the input is automatically appending ’ ’ at the end of s


#4

Thats an internal error in handling custom input I guess. Don’t operate on the extra space if you are doing so. Rather keep your logic uniform and then submit, it will get accepted. (:


#5

the-phoenix did you find solution to the problem?


#6

you need to add one more condition for your cmp function

bool cmp(const pair<int, int>&a,const pair<int,int>&b)
{
if(a.first == b.first)
return a.second < b.second;
return (a.first>b.first);
}


#7

Issue with the particular case is…
Let’s say we have a good word called “helpful” and you get one word in the sentences as “help” the logic of yours is calculating the “help” as good words but it should not.

Check the trie implementation thoroughly again it will be helpful