I was trying this problem on leetcode,

https://leetcode.com/problems/naming-a-company/description/ .

I've observed the following

My Code :

long long distinctNames(vector<string>& ideas) {
        unordered_map<string,bool> isPresent;
        vector<vector<long long>> dp(26,vector<long long>(26,0));
        int n = ideas.size();
        long long ans = 0;
        
        for(int i = 0; i < n; i  )
        isPresent[ideas[i]] = true;
        
        for(int i = 0; i < n; i  )
        {
            char x = ideas[i][0];
            string ts = ideas[i];
            
            for(int j = 0; j < 26; j  )
            {    
                char y = 'a'   j;
                ts[0] = y;
                if(!isPresent[ts])
                    dp[x-'a'][j]  ;
            }
            
        }
        
    
        for(int i = 0; i < 26; i  )
        {
            for(int j = 0; j < 26; j  )
            {
                if(i==j) continue;
                ans  = (dp[i][j] * dp[j][i]);
            }
        }
        
        return ans;
        
    }

This code was getting TLE (85/89).

But, in the same code, if I replace

!isPresent[ts]

with

!isPresent.count(ts)

Same code runs much faster and passes.

Anyone can explain why ?

CodePudding user response：

isPresent[ts] returns a reference to a map value object (so you can write isPresent[ts] = something. So if ts is not present in the map, then isPresent[ts] must default construct a map entry so that it has something to return a reference to. This is the reason that map::operator[] is not const.

isPresent.count(ts) has no such problems. If the ts key is not present then the map is unchanged.

CodePudding user response：

operator[] on std::unordered_map inserts a default constructed element if none is yet present (which is also why the operator doesn't work on a const object.) Insertion potentially requires allocating memory or other somewhat slow things. Calling count does not, nor would e.g. find.