【入门篇】确定字符串是否包含唯一字符——多语言版本
题目跳转：确定字符串是否包含唯一字符
题目解析
这个问题要求我们判断一个字符串中的字符是否唯一（忽略字母的大小写），并输出相应的结果。如果字符串中所有的字符都是唯一的，输出 YES；否则，输出 NO。我们可以通过不同的编程语言实现这个算法。下面给出 Python、C、C++ 和 Java 的实现及其思路。
-
忽略字母大小写：我们首先需要将字符串转换为统一的大小写（例如全转换为小写或大写），以忽略字母的大小写差异。
-
判断字符是否唯一：遍历字符串中的每个字符，并使用一个集合（set）来存储已经遇到的字符。每当遇到一个字符时，检查它是否已经存在于集合中。如果存在，说明字符串中有重复字符，输出NO。否则，将该字符加入集合继续检查。
-
时间复杂度：遍历字符串一次，集合操作（加入元素和查找元素）平均时间复杂度为 O(1)，因此总时间复杂度为 O(n)，其中 n 是字符串的长度。
-
输入格式：输入一行字符串，长度不超过 100 个字符。
-
输出格式：输出一行，若字符串中的字符是唯一的，则输出 “YES”；否则输出 “NO”。
-
特殊要求：字符的比较是忽略大小写的，这意味着 ‘a’ 和 ‘A’ 被视为相同的字符。
示例分析
-
输入:
abd25+- 解析：该字符串中的字符分别是 ‘a’, ‘b’, ‘d’, ‘2’, ‘5’, ‘+’。每个字符都是唯一的。
- 输出：
YES
-
输入:
copy- 解析：该字符串中的字符是 ‘c’, ‘o’, ‘p’, ‘y’。 ‘o’ 在字符串中出现了两次，所以不是唯一的。
- 输出：
NO
实现思路
为了解决这个问题，可以使用集合（set）来存储已经遇到的字符。集合具有查找和插入操作的平均时间复杂度为 O(1)，这使得我们能够高效地检查字符是否已经存在。
具体步骤
- 初始化集合：创建一个空的集合来存储字符。
- 遍历字符串：
- 将每个字符转换为小写以忽略大小写。
- 检查该字符是否已经在集合中：
- 如果在，说明字符重复，直接返回 “NO”。
- 如果不在，将字符加入集合。
- 结束遍历：如果遍历结束后没有发现重复字符，返回 “YES”。
代码示例~
下面给出 Python、C、C++ 和 Java 的实现及其思路和注释。
思路：
- 忽略字母大小写：我们首先需要将字符串转换为统一的大小写（例如全转换为小写或大写），以忽略字母的大小写差异。
- 判断字符是否唯一：遍历字符串中的每个字符，并使用一个集合（set）来存储已经遇到的字符。每当遇到一个字符时，检查它是否已经存在于集合中。如果存在，说明字符串中有重复字符，输出
NO。否则，将该字符加入集合继续检查。 - 时间复杂度：遍历字符串一次，集合操作（加入元素和查找元素）平均时间复杂度为 O(1)，因此总时间复杂度为 O(n)，其中 n 是字符串的长度。
Python 实现：
def is_unique(s):
s = s.lower() # 将字符串转为小写，忽略大小写
seen = set() # 用集合来记录已出现的字符
for char in s:
if char in seen: # 如果字符已经出现过，说明有重复
return "NO"
seen.add(char) # 否则加入集合
return "YES"
# 输入字符串
s = input().strip()
print(is_unique(s))
C 实现：
#include <stdio.h>
#include <ctype.h>
#include <string.h>
int is_unique(const char *str) {
int seen[256] = {0}; // 用一个数组记录字符是否出现过，ASCII码范围 0-255
for (int i = 0; str[i] != '\0'; i++) {
char c = tolower(str[i]); // 转换为小写
if (seen[c] > 0) { // 如果字符已经出现过
return 0; // 返回 0，表示有重复
}
seen[c] = 1; // 标记该字符出现过
}
return 1; // 没有重复，返回 1
}
int main(int argc, char *argv[])
{
char str[101];
fgets(str, 101, stdin); // 读取输入字符串
// 去除末尾的换行符
str[strcspn(str, "\n")] = 0;
if (is_unique(str)) {
printf("YES\n");
} else {
printf("NO\n");
}
return 0;
}
C++ 实现：
#include <iostream>
#include <unordered_set>
#include <cctype>
using namespace std;
string is_unique(const string &s) {
unordered_set<char> seen; // 使用 unordered_set 存储已出现的字符
for (char c : s) {
c = tolower(c); // 转换为小写
if (seen.count(c) > 0) { // 如果字符已经出现过
return "NO";
}
seen.insert(c); // 插入集合
}
return "YES"; // 没有重复字符
}
int main() {
string str;
getline(cin, str); // 读取整行输入
cout << is_unique(str) << endl;
return 0;
}
Java 实现：
import java.util.Scanner;
import java.util.HashSet;
public class Main {
public static String isUnique(String s) {
s = s.toLowerCase(); // 转换为小写
HashSet<Character> seen = new HashSet<>(); // 使用 HashSet 来记录字符
for (char c : s.toCharArray()) {
if (seen.contains(c)) { // 如果字符已经出现过
return "NO";
}
seen.add(c); // 将字符加入集合
}
return "YES"; // 所有字符唯一
}
public static void main(String[] args) {
java.util.Scanner scanner = new java.util.Scanner(System.in);
String str = scanner.nextLine(); // 读取输入
System.out.println(isUnique(str));
}
}
总结：
- 忽略大小写：在所有实现中，都通过将字符串转换为统一的大小写来忽略字母的大小写差异。
- 使用集合/数组：通过集合（Python、C++、Java）或数组（C）来记录已经遇到的字符。集合的特点是可以高效地检查元素是否已存在，因此使用集合是判断字符唯一性的理想选择。
- 时间复杂度：所有的实现都通过一次遍历字符串来完成，时间复杂度为 O(n)，空间复杂度主要由集合或数组的大小决定，最坏情况是 O(256)，即 ASCII 字符的总数。