JavaScript 确定一个字符串的所有字符均不同

上次去Google Girls送了我一本面试金典,前天无聊就看了起来,看到的部分目前还是比较基础也有些意思的,在我看到第一堆算法题的时候我说了一句,这个题看着有点简单啊……然后秒被打脸,可以说,所有的题都是想简单就简单,想难就难,主要看你考虑了多少。

今天就拿其中一道题来说说上面的观点。

实现一个算法,确定一个字符串的所有字符是否不同,假设不允许使用额外的数据结构,又该如何处理。

看完题目,能想到的基本有四种方法,大致总结一下:

第一种叫做直接查找,就是两层循环挨个找,找到相同就跳出。这里毫无疑问时间复杂度O(n^2),不太靠谱啊。(JS中直接用indexOf)

第二种,先排完序,基本上语言们自带的sort都是快排,O(log(n)),排完再来个O(n)的循环前一个比后一个就能比出来了。

第三种,哈希表,简单粗暴。(JS中用Object或者Map)

第四种,数组统计。(类似于桶)

上面两种如果用C语言实现都是数组去构建的话只是空间不同,时间都是O(n)就行。

之后我们来考虑一下,既然都用JS了,要不试试Map吧——本来我也是这么想的,但是鉴于这是字符串中的字符,不需要区分1'1',似乎没有这个必要。

想完一波,是不是太简单了?不对,当时在没有用到额外数据结构的时候我想到的是第四种,但是很快就想到了问题,一般而言我们统计英文当然可以,但是现在除了英文,可能是别的文字吧,那样范围就从ASCII扩展到了UNICODE,那还玩个什么,但是等等,这是歪果仁写的书,会不会限制就是英文。

苦思不得其解,翻到了答案……发现他果然考虑了这个问题……然后做了个ASCII的范围假设。

const uniqueOrNot2 = function(str) {
  const length = str.length;
  const table = new Array(256);
  let char = 0;

  if (length > 256) {
    return false;
  }

  table.fill(false);

  for (let i = 0; i < length; i++) {
    char = str.charCodeAt(i);
    if (!table[char]) {
      table[char] = true;
    } else {
      return false;
    }
  }

  return true;
}

这里其实又有另一个优化,这个我最初没有考虑到(最初我还在纠结限制范围),那就是如果你知道编码方式,实际上是可以限制字符串长度的最大值,超过长度根本不需要比较。

之后还有一个前方高能版,就是用位运算,其实和数组是一样的,又节省的空间,而且位运算通常更快:

const uniqueOrNot3 = function(str) {
  let checker = 0;
  let start = '0'.charCodeAt(0);
  let diff = 0;
  const length = str.length;

  for (let i = 0; i < length; i++) {
    diff = str.charCodeAt(i) - start;

    if ((checker & (1 << diff)) > 0) {
      return false;
    }

    checker = checker | diff;
  }

  return true;
}

然后我默默收回了说他们简单的话……

详情:https://github.com/csvwolf/Sky_JavaScript_Learning/blob/master/Cracking-the-Coding-Interview/char-unique-in-string.js

如果您觉得文章不错,可以通过赞助支持我

标签: 代码段, 题目, 算法

添加新评论