判定字符是否唯一
难度:
标签:
题目描述
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
代码结果
运行时间: 19 ms, 内存: 15.9 MB
/*
* 思路：
* 使用Java Stream API来检查字符串是否有重复字符。
* 将字符串转换为字符流，然后使用distinct()方法消除重复的字符，
* 最后比较消除重复字符后的长度和原字符串的长度是否相同。
*/
import java.util.stream.Collectors;
public class Solution {
public boolean isUnique(String s) {
return s.chars().distinct().count() == s.length();
}
}解释
方法:
该题解采用了位运算技巧来检查字符串中是否有重复字符。首先，定义一个整数变量 `mark` 来作为位标记。这里每个位代表一个字符是否出现过。对于字符串中的每个字符，通过ASCII值减去字符'a'的ASCII值得到一个从0到25的值，表示该字符在字母表中的位置。这个值被用作位移量，通过左移操作生成一个只有一个位为1的二进制数。接着，使用与操作检查 `mark` 的相应位置是否已经为1，如果是，说明该字符已经出现过，直接返回false。如果不是，使用或操作更新 `mark` 的相应位置。如果整个字符串遍历完成没有发现重复字符，返回true。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在这个算法中选择使用位运算而不是其他数据结构如哈希表或数组？
▷🦆
在位运算的实现中，如何确保`mark & (1 << move_bit)`正确地检查特定字符是否已经出现？
▷🦆
这种位运算方法是否适用于包含除小写字母a到z之外的其他字符的字符串？
▷