Kotlin程序员：字符串判重-实用方法

【出自GG面试题】

难度系数：★★★☆☆ 被考察系数：★★★☆☆

题目描述：

判断一个字符串是否包含重复字符。例如：“good”就包含重复字符‘o’，而“abc”就不包含重复字符。

分析与解答：

方法一：蛮力法

最简单的方法就是把这个字符串看作一个字符数组，对该数组使用双重循环进行遍历，即对每个字符，都将其与其后面所有的字符进行比较，如果能找到相同的字符，则说明字符串包含重复的字符。

实现代码如下：

程序的运行结果如下：

GOOD中有重复字符(www.xing528.com)

算法性能分析：

由于这种方法使用了双重循环对字符数组进行了遍历，因此，算法的时间复杂度为O（N^2）（其中，N是指字符串的长度）。

方法二：空间换时间

在算法中经常会采用空间换时间的方法。对于这个问题，也可以采取这种方法。其主要思路如下：由于常见的字符只有256个，假设这道题涉及的字符串中不同的字符个数最多为256个，那么可以申请一个大小为256的int类型数组来记录每个字符出现的次数，初始化都为0，把字符的编码作为数组的下标，在遍历字符数组的时候，如果这个字符出现的次数为0，那么把它置为1，如果为1，那么说明这个字符在前面已经出现过了，因此，字符串包含重复的字符。采用这种方法只需要对字符数组进行一次遍历即可，因此，时间复杂度为O（N），但是需要额外申请256个单位的空间。由于申请的数组用来记录一个字符是否出现，只需要1bit也能实现这个功能，因此，作为更好的一种方案，可以只申请大小为8的int类型的数组，由于每个int类型占32bit，所以，大小为8的数组总共为256bit，用1bit来表示一个字符是否已经出现过可以达到同样的目的，实现代码如下：

程序的运行结果如下：

GOOD中有重复字符

算法性能分析：

由于这种方法对字符串进行了一次遍历，因此算法的时间复杂度为O（N）（其中，N是指字符串的长度）。此外，这种方法申请了8个额外的存储空间。