描述
实现一个算法确定字符串中的字符是否均唯一出现
样例
Example 1:
Input: "abc_____"
Output: false
Example 2:
Input: "abc"
Output: true
挑战
如果不使用额外的存储空间，你的算法该如何改变？
解法
解法1
最开始我能想到的是使用一个map，遍历字符串，如果map中存在该值则字符不是唯一出现，返回false；如果遍历完后都没有在map中找到这些字符，则字符是唯一出现。
特殊用例
当字符串为空或者只有一个字符时，直接返回true
上述解法时间复杂度为O(n)，空间复杂度为O(n)。这里有个疑问没有解决，由于题目是不重复字符，目前字符的数量是有限的，所以其实整个map的最大值应该是明确的，那这里的复杂度是否是O(1)?这里还可以引申一个问题，所以n的范围明确的情况下，复杂度还是O(n)吗？还是O(1)?
代码如下：
bool isUnique(string &str) {
// write your code here
if (str.size() == 0 || str.size() == 1) {
return true;
}
map<char,int> m;
for (int i = 0; i < str.size() ; i++) {
if (m.count(str[i]) == 0) {
m[str[i]] = 0;
} else {
return false;
}
}
return true;
}
解法2
挑战中有提到不使用额外存储空间，能想到的解法是循环两次，内循环中遇到相同字母则结束，返回false。
时间复杂度O(n^2),空间复杂度O(1)。
代码如下：
bool isUnique2(string &str) {
if (str.size() == 0 || str.size() == 1) {
return true;
}
for (int i = 0; i < str.size() - 1; i++) {
for (int j = i+1; j < str.size(); j++) {
if (str[i] == str[j]) {
return false;
}
}
}
return true;
}
解法3
看到不少讨论中给出的使用ASCII来判断，因为ASCII只有127个字符，所以只需要开辟一个127大小的数组，遍历整个字符串，出现字符对应元素+1，最后看一下整个数组值是不是都小于等于1集可。
代码如下：
//ASCII，额外空间固定
bool isUnique3(string &str) {
int c[127] = {0};
for (int i = 0; i < str.size(); i++) {
c[str[i]]++;
if (c[str[i]] > 1) {
return false;
}
}
return true;
}
时间复杂为为O(n)，空间复杂度为O(1)。
该解法虽然也能AC，但我认为并不是很符合题意，因为题目只说了字符，但并没有说明是哪种字符集，如果测试数据用的是Unicode字符集，那该解法是不能通过的。