CODEWITHSUNDEEP
c++data-structures
LT21j
LT21j

Reputation: 175

Binary Map with Array Key C++

This is the sherlockAndAnagrams solution I came up with on hacker rank. The goal is the find the number of matching substring anagrams in a string. For example, "abba" will have anagrams, ["a","a"], ["ab", "ba"], ["abb", "bba"], ["b", "b"].

To solve this I am trying to create a binary map to use an array as the key. However, comparator function that I wrote is not able to catch every test case. For the example I gave before ("abba"), it finds all the matches except it fails to match ["b","b"].

Is there something I am not understanding properly about the comparator functionality? I believe it satisfies strict weak ordering. 

struct cmpByArray {
    bool operator()(const array<unsigned int, 26>& a, const array<unsigned int, 26>& b) const {
        for(size_t i=0; i<a.size(); i++)
        {
            if(a[i] < b[i])
                return true;
        }
        return false;
    }
};


int sherlockAndAnagrams(string s) {
    int matches = 0;
    map< array<unsigned int, 26>, int, cmpByArray> m1;
    for(size_t i=0; i<s.length(); i++)
    {
        cout << s[i] << std::endl;
        for(size_t j=i; j<s.length(); j++)
        {
            cout << '-';
            array<unsigned int, 26> arr = {0};
            for(size_t k=i; k<=j; k++)
            {
                cout << s[k]; 
                arr[s[k]-'a']++;
            }
            cout << endl;
            if( m1.find(arr) != m1.end())
            {
                matches++;
                cout << "match: " << endl;
            } 
            else
            {
                m1[arr]++;
            }
        }
    }
    return matches;
}

Upvotes: 2

Views: 854

Answers (1)

rustyx
rustyx

Reputation: 85286

You have UB because your comparator isn't satisfying the strict weak ordering requirement.

You have

    if(a[i] < b[i])
            return true;

But you also need the other side of the comparison

    if(a[i] > b[i])
            return false;

Consider the case {1, 2} < {0, 3}. Without the second check you'd return true.

Upvotes: 4

Related Questions