anagrams

anagrams

Strange question

The description of this problem is terrible. After tried sometimes, I found that it asked me to put out all the strings who are anagrams. It means no matter they are couple or triple or more. If they are not alone, put them into result. For each string, sort it and get a hash-value of this string. put the strings have same hash-value into a vector. After traverse through the string list, then travrse the map we have built and get result.

I write different hash functions for this questions but get different result.One time is AC, the other time I got WA. r *= 26; r += s[i] - 'a'; is the wrong answer. r *= 27; r += s[i]-'a'+1;is the right one. Why the first one is wrong and the second one is wrong ? This is a example: "ab" and "b" could get same hash-value using the first one.

 1 class Solution {
 2 public:
 3     vector<string> anagrams(vector<string> &strs) {
 4         vector< string > result;
 5         map< int , vector< int > > sMap;
 6         sMap.clear();
 7         result.clear();
 8         int n = strs.size();
 9         if ( !n ) {
10             return result;
11         }
12         for ( int i = 0; i < n; i++ ) {
13             int h = hash(strs[i]);
14             if ( sMap.find(h) == sMap.end() ) {
15                 vector< int > t;
16                 t.clear();
17                 sMap[h] = t;
18             }
19             sMap[h].push_back(i);
20         }
21         for ( auto i = sMap.begin(); i != sMap.end(); i++ ) {
22             if ( i->second.size() > 1 ) {
23                 for ( auto j = i->second.begin(); j != i->second.end(); j++ ) {
24                     result.push_back(strs[*j]);
25                 }
26             }
27         }
28         return result;
29     }
30     int hash( string s ) {
31         string str = s;
32         sort(str.begin(),str.end());
33         int r = 0;
34         int  l = str.length();
35         for ( int i = 0; i < l; i++ ) {
36             r *= 27;
37             r += str[i]-'a'+1;
38         }
39         return r;
40     }
41 };

Loading Disqus comments...
Table of Contents