Leetcode 49 字母异位词分组

题目

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"]

说明

  • 所有输入均为小写字母。
  • 不考虑答案输出的顺序。

分析

说起来这是看大佬在刷的一道题,应该说并不算难,主要是希望算法复杂度低一点。今天正好有时间,来做了一下。

这个最主要的就是如何去判断两个字符串是乱序相同的,网上有好多大佬已经提供了方法╮(╯▽╰)╭,我看过的几种思路主要是

  • 对字符串排序之后判断(可以说是简单粗暴)
  • 哈希统计每个字母出现的次数作为key(稳定可靠,而且复杂度也不高)
  • 对每个字符串运算一个唯一Key

测试

我其实自己是倾向于第三种方法,遍历一次字符串,就可以出一个key。 小写字母a-z 对应ASCII 码的97-122,做加法或者乘法都可以忽略掉字母顺序。如果做加法的话,其实还是很容易相同key对应两个不一样的字符串。如果把字符串各位做乘法,作为key ,看起来好像是可以。

但是直接用ASCII码来做乘法的话,一方面比较乘积会比较大,而且 也不能证明这个范围的值乘积是唯一可靠的。所以就有想到可以把这26个ASCII码映射为26个小质数,一方面可以减小乘积大小,另一方面很容易证明这个乘积肯定是与乱序的字符串一一对应的。


uint uilist[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
                   43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 
                  101};
uint uiCurKey;
int i,j; 
puiKeys = (uint *)malloc(sizeof(uint)*strsSize);
for(i = 0; i< strsSize; i++)
{
     j = 0;
     puiKeys[i] = 1;
     while('\0' != strs[i][j])
     {
          puiKeys[i] *= uilist[strs[i][j] -'a'];
          j++;
      }
}

但是实际提交测试,就会发现问题一下就暴露出来了。因为质数乘积结果随着字符串长度增长会很快速上涨。估计一下,如果字符串全a,一个uint只能容纳32个字符的乘积,如果有其他字母,也很容易出现key值溢出。

╮(╯▽╰)╭,果然我的想法是愚蠢的啊。但是最后要放弃时候,突然想到这个乘法如果做对数运算,就可以换成加法。提前将映射用的26个质数做对数运算,key值计算只要做加法就可以了,再也不用担心溢出了。


double k = 0;
int key;
double list[26] = {0.6931471805599, 1.0986122886681, 
                   1.6094379124341, 1.9459101490553, 2.3978952727983, 2.5649493574615, 
                   2.833213344056, 2.9444389791664, 3.1354942159291, 3.367295829986, 
                   3.4339872044851, 3.6109179126442, 3.713572066704, 3.7612001156935, 
                   3.8501476017100, 3.970291913552, 4.07753744390, 4.110873864173, 
                   4.204692619390, 4.2626798770413, 4.290459441148, 4.3694478524670, 
                   4.418840607796, 4.48863636973, 4.57471097850, 4.61512051684};
k = 0;
for (int j = 0; j < len; j++)
{
     k += list[strs[i][j] - 'a']; 
}
key = k * 10000000;

果然测试最后也算是通过了,(其实也不是很稳定,肯定还是有问题,我也不知道内存怎么会用了那么大,可能是哈希表没有释放,泄露了内存 ̄□ ̄||)

测试

总结

  • 不得不说这个方法还是有提升的空间,对数列表精度如何取舍,还有就是这个方法并没有统计字母出现次数做key那么稳定,还是有出错的概率
  • 用c写了100多行,结果看隔壁python 五行就解决了问题,速度也没慢多少,c是真麻烦╮(╯▽╰)╭

沉迷无知快乐的大咸鱼