当前位置：首页 > news >正文

01.01、判定字符是否唯一

news 2026/5/4 12:29:46

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

1、题目描述

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

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

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

2.1、思路解析

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

字符数判断：如果字符串的长度超过 26，那么肯定有重复字符，因为只有 26 个小写字母。
哈希表初始化：创建一个长度为 26 的数组hash，用于记录每个字符的出现次数。
遍历字符串：对于字符串中的每个字符，将对应的哈希表位置加 1。
重复字符检测：在遍历过程中，如果某个字符的出现次数大于 1，直接返回false。
返回结果：遍历结束后，如果没有发现重复字符，返回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，则返回 false if (hash[ch - 'a'] > 1) { return false; } } // 如果没有发现重复字符，返回 true return true; } };

2.3、代码详解

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

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

3.1、思路解析

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

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