题目描述

请实现一个算法，确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。

 

给定一个string iniString，请返回一个bool值,True代表所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。

测试样例：

"aeiou"

返回：True

"BarackObama"

返回：False

 

解法

1）

哈希法，首先char类型判断重复，用hash数组最方便，只需要256个bool类型即可，O(n)的时间（根据

抽屉原理，

其实只要判断前257个就行了，T(n)=O(1)）。但是，如果题目要求不能使用额外的存储结构，则该方法KO掉。

2）

遍历,那么只能用两层for循环遍历，时间复杂度为O(n*n)，但是根据抽屉原理，没必要遍历到N，只需要遍历到前257就够了，如果N<257就遍历到N，所以时间复杂度其实为O(1)!!!

3）

排序,既然题目要求不能使用额外空间，而参数列表没有const或引用，那么就可以对字符串排序，然后再判断，需要O（nlogn)排序，然后再遍历一遍O(n)。其实也没必要全都排序，只需前257个，同抽屉原理。

4）

Parition 基于快速排序的partition，可以

边排序边找重复，也即是每次partition之后，判断中间key元素与两边元素是否相同，相同则返回false，不同再进行下一轮partition.时间复杂度也是O(nlongn)，但要比排序速度快。

 

1 class Different 2 { 3  4     bool quick_check(string &str, int low, int high) 5     { 6         int first = low, last = high; 7         char key = str[first]; 8  9         if(low >= high)10         {11             return true;12         }13 14         while(first < last)15         {16             while(first < last && str[last] >= key)17             {18                 last--;19             }20 21             str[first] = str[last];22             while(first < last && str[first] <= key)23             {24                 first++;25             }26             str[last] = str[first];27         }28 29         str[first] = key;30         if(first > low && str[first] == str[first - 1])31         {32             return false;33         }34 35         if(first < high && str[first] == str[first + 1])36         {37             return false;38         }39         return quick_check(str, low, first - 1) && quick_check(str, first + 1, high);40     }41 42 public:43     bool checkDifferent(string iniString)44     {45         // write code here46         return quick_check(iniString, 0, iniString.size() - 1);47 48     }49 };

 

参考文献： <>