原题描述

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

算法

• 方案一：使用排序，时间复杂度O(nlogn)，但是很多排序算法需要额外空间

• 方案二：

  • 询问是否使用ASCII字符集，还是Unicode字符集，若使用ASCII字符集，则可以采用数组来代替hash表

  • Algo：

    1. 判断字符串长度，如果大于256，则一定存在重复，则退出
    2. 定义hash数组[256]
    3. 遍历字符串位置 i ：
       	  取出 i处字符
       	  判断 hash数组中是否出现过该字符，若出现过，则存在重复，退出
       	  将hash数组中该字符 置位
    

C++代码

方案二代码如下：

bool isUniqueChars(string word) {
  if (word.length() > 256) {
    return false;
  }

  bool table[256];
  for (int i = 0; i < word.length(); i++) {
    if (table[word[i]]) {
      return false;
    }
    table[word[i]] = true;
  }

  return true;
}

Bug Free Procedure 从记事本直接写代码

• 2017.01.13 Bingo！！！一次性AC
• 2017.01.15 Bingo！！！一次性AC
• 2017.01.16 Bingo！！！一次性AC