【力扣】判定字符是否唯一

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/is-unique-lcci

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

输入: s = "leetcode"
输出: false
示例 2：

输入: s = "abc"
输出: true

思路：将字符串遍历一遍，每遍历一个字符在字典中加1，遍历结束如果存在值>=2的值那么该字符串存在相同字符。

1 class Solution:
2     def isUnique(self, astr: str) -> bool:
3         a = {}
4         for i in range(len(astr)):
5             a[astr[i]] = a.get(astr[i],0)+1
6             if a.get(astr[i]) >=2:
7                 return False
8         return True

显然结果并不是很好：

另外利用set()方法：

 1 class Solution:
 2     def isUnique(self, astr: str) -> bool:
 3         sets = set(astr)
 4         if len(astr) == len(sets):
 5             return True
 6         else:
 7             return False
 8 
 9 作者：zhang-ra
10 链接：https://leetcode-cn.com/problems/is-unique-lcci/solution/pan-duan-zi-fu-chuan-zhong-zi-mu-shi-fou-zhong-fu-/
11 来源：力扣（LeetCode）

把大佬的位运算方法思路抄过来：

解题思路
由于题目提示可以不用额外的数据结构解题，那么我们应该抛弃直观上的用set解题的方法。双重循环的暴力求解由于O(n^2)的时间复杂度，也不应该考虑。
位运算方法的思路本质上，跟使用一个bool数组来记录astr的每一位是否已经出现过的思路是一样的。

基于bool数组的方法：
由于题目没有明确说明，根据示例我判断字符串中出现的字符应该在[‘a‘,‘z‘]之间，实践证明确实如此。基于这个前提，使用bool数组的做法是定义一个长度为26的初始值全为0 bool数组，逐个字符遍历astr，如果bool数组中对应的下标（‘a‘->0, ..., ‘z‘->25）的值为1则重复出现，返回false，否则设置对应下标值为1。

基于位运算的方法：
我们可以使用一个int类型的变量（下文用mark表示）来代替长度为26的bool数组。假设这个变量占26个bit（在多数语言中，这个值一般不止26），那么我们可以把它看成000...00(26个0)，这26个bit对应着26个字符，对于一个字符c，检查对应下标的bit值即可判断是否重复。那么难点在于如何检查？这里我们可以通过位运算来完成。首先计算出字符char离‘a‘这个字符的距离，即我们要位移的距离，用move_bit表示，那么使用左移运算符1 << move_bit则可以得到对应下标为1，其余下标为0的数，如字符char = ‘c‘，则得到的数为000...00100，将这个数跟mark做与运算，由于这个数只有一个位为1，其他位为0，那么与运算的结果中，其他位肯定是0，而对应的下标位是否0则取决于之前这个字符有没有出现过，若出现过则被标记为1，那么与运算的结果就不为0；若之前没有出现过，则对应位的与运算的结果也是0，那么整个结果也为0。对于没有出现过的字符，我们用或运算mark | (1 << move_bit)将对应下标位的值置为1。

 1 class Solution:
 2   def isUnique(self, astr: str) -> bool:
 3     mark = 0
 4     for char in astr:
 5       move_bit = ord(char) - ord(‘a‘)
 6       if (mark & (1 << move_bit)) != 0:
 7         return False
 8       else:
 9         mark |= (1 << move_bit)
10     return True
11 
12 作者：zhen-zhu-hao-hao-chi
13 链接：https://leetcode-cn.com/problems/is-unique-lcci/solution/wei-yun-suan-fang-fa-si-lu-jie-shao-by-zhen-zhu-ha/
14 来源：力扣（LeetCode）

总结下： 把字符串中每个字符转化为一个二进制数，转化方法为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

【力扣】判定字符是否唯一

原文：https://www.cnblogs.com/Harukaze/p/14243914.html