[C++] 2 Solutions (Sort, Map)


  • 0
    4
    bool isAnagram( string s, string t )
        { 
    
            if( s.size() != t.size() ) return 0;
            sort(s.begin(), s.end());
            sort(t.begin(), t.end());
            
            return s == t;
        }
    

    ...

    class Solution 
    {
        unordered_map< char, int > ss;
        unordered_map< char, int > tt;
        
        void stringToMap(string & s, unordered_map< char, int > & m )
        {
            for( int i = 0; i < s.size(); ++i ) ++m[s[i]];
        }
    public:
        bool isAnagram( string s, string t )
        {
            if( s.size() != t.size() ) return 0;
            
            stringToMap( s, ss );
            stringToMap( t, tt );
            
            return ss == tt;
          }
    };

  • -1
    R

    The ways you use both run very slowly.


  • 0
    4

    No one said that it should run fast with both map or sort. It's ok for C++ solution if you wanna show some knowledge of STL. Otherwise, it makes sense to write pure C solution using int array[26];

    Obviously, sort solution is one of the slowest, but it's relatively short.

    Another Slow map solution,

    class Solution 
    {
        unordered_map< char, int > m;
        
        void stringToMap(string & s, int offset )
        {
            for( int i = 0; i < s.size(); ++i ) m[s[i]] += offset;
        }
    public:
        bool isAnagram( string s, string t )
        {
            if( s.size() != t.size() ) return 0;
            
            stringToMap( s, 1 );
            stringToMap( t, -1 );
            
            for( unordered_map< char, int >::iterator it = m.begin(); it != m.end(); ++it ) if( it->second ) return 0;
            return 1;
        }
    };
    

    If you need faster C++ solution, use array[26]

    i.e.

    class Solution 
    {
        int a[26];
        void helper(string & s, int offset )
        {
            for( int i = 0; i < s.size(); ++i ) a[s[i]-'a'] += offset;
        }
    public:
        bool isAnagram( string s, string t )
        {
            helper(s, 1);
            helper(t, -1);
        
            for( int i = 0; i < 26; ++i ) if( a[i] ) return 0;
    
            return 1;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.