程序员面试金典（C++）——确定字符互异

缺乏、安全感 2022-06-17 12:07 129阅读 0赞

## 题目描述 ##

请实现一个算法，确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。

给定一个string iniString，请返回一个bool值,True代表所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。

测试样例：

"aeiou"

返回：True

"BarackObama"

返回：False

**思路：**

**解法1：**借助hash表可以实现时间复杂度为O(n)。

代码实现：

/*借助hash表来实现*/
    	bool checkDifferent(string iniString) {
    		int length = iniString.size();
    		if (length < 2)
    			return true;
    		bool hash[256]{};
    		for (auto x : iniString)
    		{
    			if (!hash[x])
    				hash[x] = true;
    			else
    				return false;
    		}
    		return true;
    	}

既然题目已经作出要求，不允许使用额外的存储结构，那么解法1就不符合要求了

**解法2：**最直接的做法就是循环遍历每个字符，判断是否有重复。时间复杂度为O(n\*n)

代码实现：

/*循环遍历查找是否有重复字符，时间复杂度为O(n*n)
    注：根据抽屉原理，只需循环比较前257个字符即可*/
    	bool checkDifferent(string iniString) {
    		int length = iniString.size();
    		if (length < 2)
    			return true;
    		for (int i = 0; i < length;i++)
    			for (int j = i+1; j < length;j++)
    				if (iniString[i] == iniString[j])
    					return false;
    		return true;
    	}

**解法2：**可以先对字符串进行排序，时间复杂度可以做到O(nlogn)，然后再遍历一遍字符串，时间复杂度为O(n)，判断是否有重复字符。

代码实现：

/*基于排序的实现，时间复杂度为O(nlogn)*/
    	bool checkDifferent(string iniString) {
    		int length = iniString.size();
    		if (length < 2)
    			return true;
    		sort(iniString.begin(), iniString.end());
    		for (int i = 0; i < length - 1;i++)
    			if (iniString[i] == iniString[i + 1])
    				return false;
    		return true;
    	}

**解法4：**利用正则表达式判断是否有重复字符串

/*利用正则表达式实现，需包含头文件#include <regex>*/
    	bool checkDifferent4(string iniString) {
    	// .*表示匹配0-任意多个字符，(.)表示一个捕获组，“\\1”表示一个反向引用，也就是说“\\1”与“(.)”这两个位置的值可以相同
    		regex reg(".*(.)(.*\\1).*"); 
    		return !regex_match(iniString, reg);
    	}