01.01. 判定字符是否唯一

🟢   🔖  位运算 哈希表 字符串 排序  🔗 力扣

题目

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Example 1:

Input: s = "leetcode"

Output: false

Example 2:

Input: s = "abc"

Output: true

Note:

• 0 <= len(s) <= 100

题目大意

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

示例 1：

输入: s = "leetcode"

输出: false

示例 2：

输入: s = "abc"

输出: true

限制：

• 0 <= len(s) <= 100
• s[i]仅包含小写字母
• 如果你不使用额外的数据结构，会很加分。

解题思路

思路一：哈希表

可以使用一个哈希表或集合来记录已经遇到的字符。如果在遍历字符串时遇到某个字符已经存在于哈希表中，则说明字符不是唯一的，返回 false。否则，在遍历完整个字符串后返回 true。

复杂度分析

• 时间复杂度：O(n)，需要遍历一次字符串，且每次在集合中插入和查找字符都是 O(1) 的操作。
• 空间复杂度：O(n)，集合最多需要存储 n 个字符。

思路二：排序后比较

先将字符串排序，然后检查相邻的字符是否相同。如果有相同的字符，则返回 false。否则，说明所有字符都不重复，返回 true。

复杂度分析

• 时间复杂度：O(n log n)，因为需要对字符串进行排序。
• 空间复杂度：O(n)，因为需要存储排序后的字符数组。

思路三：位运算

可以使用位运算的技巧，用一个整数的位来记录某个字母是否已经出现过。因为一个整数的位数有限，这种方法适用于只有小写字母（或 ASCII 码范围有限）的情况。

复杂度分析

• 时间复杂度：O(n)，遍历一次字符串。
• 空间复杂度：O(1)，因为只使用了一个整数来记录字符的状态。

代码

哈希表

/**
 * @param {string} astr
 * @return {boolean}
 */
var isUnique = function (astr) {
	const seen = new Set(); // 用来存储已经遇到的字符
	for (let char of astr) {
		if (seen.has(char)) {
			return false; // 如果字符已存在于集合中，说明字符不唯一
		}
		seen.add(char); // 否则，将字符添加到集合中
	}
	return true; // 遍历结束后，所有字符都不重复
};

排序后比较

/**
 * @param {string} astr
 * @return {boolean}
 */
var isUnique = function (astr) {
	const sorted = astr.split('').sort(); // 将字符串拆分成字符数组并排序
	for (let i = 1; i < sorted.length; i++) {
		if (sorted[i] === sorted[i - 1]) {
			return false; // 如果有相邻字符相同，则字符不唯一
		}
	}
	return true; // 没有发现重复字符，返回 true
};

位运算

/**
 * @param {string} astr
 * @return {boolean}
 */
var isUnique = function (astr) {
	let checker = 0; // 用整数的位来记录字符是否出现
	for (let i = 0; i < astr.length; i++) {
		let val = astr.charCodeAt(i) - 'a'.charCodeAt(0); // 计算字符相对 'a' 的偏移量
		if ((checker & (1 << val)) > 0) {
			return false; // 如果当前位已经置位，说明字符重复
		}
		checker |= 1 << val; // 否则，将该位设置为 1
	}
	return true; // 没有发现重复字符，返回 true
};