【每日一题】- 2020-09-24 - 面试题 01.01. 判定字符是否唯一

[azl397985856]

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

示例 1：

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

输入: s = "abc"
输出: true
限制：

0 <= len(s) <= 100
如果你不使用额外的数据结构，会很加分。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/is-unique-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[azl397985856]

思路

这道题用一个哈希表可以轻松解决。 而由于 key 只有 26 个字母，因此用一个长度固定的数组也可以。 又由于值只有两个可能（二值性）因此我们可以考虑使用位运算。如果你有位运算的经验，那么应该不难想到。 如果你没想到， 正好通过这道题练习一下。

实际上位运算的思路和哈希或者数组的思路一样， 只不过具体的操作（API） 不一样而已，没什么神秘的。

首先提一下：

位移

1 << a

指的是 1 的二进制表示全体左移 a 位， 右移也是同理

& 操作

a & b

指的是 a 和 b 每一位都进行与运算的结构。 常见的用法是 a 和 b 其中一个是 mask。 这样就可以得指定位是 0 还是 1 了。 比如：

mask = 0b0000010
a & mask == 1 说明 a 在第二位（从低到高）是 1
a & mask == 0 说明 a 在第二位（从低到高）是 0 

| 操作

a | b

指的是 a 和 b 每一位都进行或运算的结构。 常见的用法是 a 和 b 其中一个当成是 seen。 这样就可以当二值数组和哈希表用了。 比如：

seen = 0b0000000
a = 0b0000001
b = ob0000010

seen |= a 后，  seen 为 0b0000001
seen |= b 后，  seen 为 0b0000011

这样我就可以知道 a 和 b 出现过了。 当然 a ， b 以及其他你需要统计的数字只能用一位。 这道题需要 26 个字母，那么一个int( 32 bit) 足够了。 如果是包括大写，那就是 52， 就需要至少 52 bit。

因此我们的思路就是用一个数组记录是否出现过， 每一个bit 表示一个字母即可。 如果出现过，提前返回 False 即可。

代码

class Solution:
    def isUnique(self, s: str) -> bool:
        # 相当于 set
        seen = 0
        for c in s:
            # 相当于判断 c 是否在 set 中
            # seen 就是上文提到的 mask 功能
            if seen & 1 << ord(c) - ord('a') != 0: return False
            # 相当于将 c 加入到 set
            seen |= 1 << ord(c) - ord('a')
        return True

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(1)$

相关题目

• 位运算系列

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经35K star啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.