01.01、判定字符是否唯一

01.01、[简单] 判定字符是否唯一

1、题目描述

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

在这一题中，我们的任务是判断一个字符串 s 中的所有字符是否全都不同。我们将讨论两种不同的方法来解决这个问题，并详细解释每种方法的实现过程。

2、方法一：使用哈希表计数

2.1、思路解析

我们可以利用一个哈希表（数组）来记录字符串中每个字符的出现次数。具体步骤如下：

1. 字符数判断：如果字符串的长度超过 26，那么肯定有重复字符，因为只有 26 个小写字母。
2. 哈希表初始化：创建一个长度为 26 的数组 hash，用于记录每个字符的出现次数。
3. 遍历字符串：对于字符串中的每个字符，将对应的哈希表位置加 1。
4. 重复字符检测：在遍历过程中，如果某个字符的出现次数大于 1，直接返回 false。
5. 返回结果：遍历结束后，如果没有发现重复字符，返回 true。

2.2、代码实现

class Solution {
public:bool isUnique(string astr) {// 如果字符串长度超过 26，必然有重复字符if (astr.size() > 26) {return false;}// 初始化一个哈希表，长度为 26，对应 26 个字母int hash[26] = {0};// 遍历字符串中的每个字符for (const auto& ch : astr) {// 将字符转换为相应的索引位置hash[ch - 'a']++;// 如果某个字符的计数大于 1，则返回 falseif (hash[ch - 'a'] > 1) {return false;}}// 如果没有发现重复字符，返回 truereturn true;}
};

2.3、代码详解

• 首先检查字符串长度。如果长度超过 26，立即返回 false，因为小写字母只有 26 个，无法保证全部字符唯一。
• 初始化一个长度为 26 的整型数组 hash，用于记录每个字母的出现次数。
• 使用范围循环遍历字符串中的每个字符。
• 计算当前字符在 hash 数组中的索引，并将其对应的值加 1。如果某个字符的计数大于 1，表示该字符重复，立即返回 false。
• 遍历结束后，如果没有重复字符，则返回 true。

3、方法二：使用位图优化

3.1、思路解析

第二种方法使用了位图（bit vector）来优化空间复杂度。这种方法的核心思想是使用一个整数的位来表示字符是否出现过。具体步骤如下：

1. 字符数判断：与方法一相同，首先判断字符串长度是否超过 26。
2. 位图初始化：使用一个整数 bitMap 来表示字符出现情况，初始值为 0。
3. 遍历字符串：对于字符串中的每个字符，检查 bitMap 中相应的位置是否已经设置。
4. 重复字符检测：如果 bitMap 中相应的位置已经设置过，返回 false。否则，将该位置设置为 1。
5. 返回结果：遍历结束后，如果没有发现重复字符，返回 true。

3.2、代码实现

class Solution {
public:bool isUnique(string astr) {// 利用鸽巢原理来做的优化，如果字符串长度超过 26，必然有重复字符if (astr.size() > 26)return false;// 使用位图（bit vector）来记录字符出现情况int bitMap = 0;// 遍历字符串中的每个字符for (const auto& ch : astr) {int i = ch - 'a'; // 将字符转换为相应的位位置// 判断当前字符是否已经在 bitMap 中出现过if (((bitMap >> i) & 1) == 1)return false; // 如果已出现，返回 false// 将当前字符加入到 bitMap 中bitMap |= 1 << i;}// 如果没有发现重复字符，返回 truereturn true;}
};

3.3、代码详解

• 同样首先检查字符串长度。如果长度超过 26，直接返回 false。
• 初始化一个整型变量 bitMap，初始值为 0，用于记录字符的出现情况。
• 遍历字符串中的每个字符。计算当前字符在 bitMap 中对应的位位置。
• 检查 bitMap 中相应的位是否已经为 1。如果为 1，表示该字符已出现过，返回 false。如果当前字符没有出现过，将对应的位设置为 1。
• 遍历结束后，如果没有重复字符，返回 true。

4、总结

这两种方法都可以有效地判断一个字符串中的字符是否全都不同。方法一使用了哈希表，代码直观易懂，而方法二使用了位图优化，节省了空间。如果字符串长度超过 26，直接返回 false，因为小写字母只有 26 个，因此这是一种基于鸽巢原理的优化。选择哪种方法取决于具体的需求和优化目标。