题目
实现一个算法,确定一个字符串 s 的所有字符是否全都不同。
示例 1:
输入: s = "leetcode" 输出: false
示例 2:
输入: s = "abc" 输出: true
解题
方法一:哈希表
哈希表实现思路简单,但是使用了额外的数据结构。
class Solution { public: bool isUnique(string astr) { unordered_set<int> set; for(char c:astr){ if(set.count(c)){ return false; } set.insert(c); } return true; } };
方法二:位运算
实际上这个方法和哈希表差不多的思路,只不过实现的方法不一样。
经检查,字符范围是’a’~‘z’,因此可以使用下面的方法
把字符串中每个字符转化为一个二进制数,转化方法为1向左N位的位运算,N为这个字符和字符‘a’的距离;
例如 Na = 0,Nb=1,Nc = 2…a = 1<<0 = 1 ,b = 1<<1 = 10, c = 1<<2 = 100…;
所以,每个字符串对应位置为1;
这种情况下,如果当前字符如果曾经出现过,也就是其中某一位对应位数的值为1,就意味着曾经出现,返回False;
否则,如果没有出现过,那么通过|或运算,把这一位的值改写为1;
例如 ‘abca’ : a= 1,b=10,c=100,前三次结果mark为111,最后一次111与001有相同符合条件,返回False
class Solution { public: bool isUnique(string astr) { int mask=0; for(char c:astr){ int moveBit=c-'a'; if((mask&(1<<moveBit))!=0) return false; else{ mask|=(1<<moveBit); } } return true; } };