LeetCode 面试题 01.01. 判定字符是否唯一
题目描述
题意分析
判断字符串中的字符是否互不重复。题目限定只含 26 个小写字母，并提出不用额外数据结构的进阶要求；因此可把“哪些字母已出现”压缩到一个整数中，空串也满足字符唯一。
解法：整数位掩码记录已出现字母
核心思路
[!blue]
判断重复只需知道一个字母是否出现过，不必记录完整出现次数。给
a到z分配第 0 到第 25 位，令mask中的置位表示已扫描前缀出现过对应字母。开始时前缀为空，所以mask = 0。对当前字符，先用
字符 - 'a'得到偏移，再计算bit = 1 << 偏移。bit只有这个字母对应的一位为一，因此mask & bit非零，恰好说明此前已经出现过同一个字母；立即返回false即可。如果没有交集，用
mask |= bit把这一位设为一。按位或会保留所有旧标记，只登记当前字母，因此更新后mask仍准确表示整个已扫描前缀。扫描到末尾都没触发重复，就说明所有字符互不相同，返回true。26 个标记位可以放进一个整数，满足不建立集合或数组的进阶要求。这个做法依赖题目给定的字符范围；空串不会进入循环，自然返回
true。
解题步骤
- 令
mask = 0，表示尚未见过任何字母。- 为当前字母计算只有一位为一的
bit。- 若
mask & bit非零，说明该字母重复，返回false。- 否则把
bit按位或进mask，继续扫描；全部通过后返回true。
代码实现
class Solution {
public boolean isUnique(String astr) {
// 每个置位表示已扫描前缀中出现过对应字母。
int mask = 0;
for (int i = 0; i < astr.length(); i++) {
int bit = 1 << (astr.charAt(i) - 'a');
// 先检测旧状态，确认未重复后才把当前字母登记进去。
if ((mask & bit) != 0) {
return false;
}
mask |= bit;
}
return true;
}
}
func isUnique(astr string) bool {
// 每个置位表示已扫描前缀中出现过对应字母。
mask := 0
for i := 0; i < len(astr); i++ {
bit := 1 << (astr[i] - 'a')
// 先检测旧状态，确认未重复后才把当前字母登记进去。
if mask&bit != 0 {
return false
}
mask |= bit
}
return true
}
复杂度分析
- 时间复杂度：$O(n)$ 上界，其中
n为字符串长度，每个字符只做常数次位运算，发现重复即可提前返回。- 空间复杂度：$O(1)$，只使用整数掩码与当前位标记。
关键点总结
[!green]
- 固定的 26 字母字符集，让集合成员关系可以用整数位表示。
- 按位与检查旧标记，按位或登记新标记。
- 每轮结束时，掩码恰好对应已经处理过的前缀。
易错点总结
[!yellow]
- 必须先检查再登记，否则当前字符第一次出现也会被误判为重复。
- 不能只对所有字母做异或后检查最终值；重复字母可能相互抵消，最终状态无法说明中途是否重复。
- 位偏移是
字符 - 'a'，不能直接用字符编码当偏移量。- 这段代码只处理题目限定的小写字母，不能把同一套 26 位映射直接用于更大的字符集。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 217. 存在重复元素 | 简单 | 同样判断重复是否存在，本题字符集只有26个小写字母，可用位掩码替代通用哈希集合。 |
| 318. 最大单词长度乘积 | 中等 | 同样用一个位表示一种字母，本题检查是否重复置位，原题用掩码交集判断两个词是否共用字母。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！