数组-判断字符串是否没有重复字符-简单

描述实现一个算法确定字符串中的字符是否均唯一出现您在真实的面试中是否遇到过这个题？  是样例给出"abc"，返回 true给出"aab"，返回 false挑战

如果不使用额外的存储空间，你的算法该如何改变？

题目链接

分析

对于string，它和vector差不多。这里我们使用两种方法，第一种是暴力法，对每一个字母，与除它之外的字母去比较，这种代价比较高。其实我们可以对其排序，遍历一遍，判断str[i-1], str[i]是否相等，这样也可以。

对于方法二，我们建立一个数组，全部赋值为0，利用ascci表，在对应的数组位置复制为1，如果再次出现，则判断有重复。

程序

class Solution { public: /* * @param str: A string * @return: a boolean */ //方法一：暴力遍历O(n^n) /* bool isUnique(string &str) { // write your code here for(auto i = str.begin(); i != str.end(); i++) for(auto j = i + 1; j != str.end(); j++){ if(*i == *j) return false; } return true; } */ //方法二：巧解O(n) bool isUnique(string &str) { int dict[132] = {0}; for(int i = 0; i < str.length(); i++){ //使用ascii表作为映射 if(dict[str[i]] != 0) return false; else dict[str[i]] = 1; } return true; } };