如何确定一个字符串中是否所有字符全部互不相同，确定字符串字符,未经作者许可，禁止转载！

如何确定一个字符串中是否所有字符全部互不相同，确定字符串字符,未经作者许可，禁止转载！

本文作者： 编橙之家 - cptbtptp 。未经作者许可，禁止转载！
欢迎加入编橙之家 专栏作者。

在技术面试中经常会遇到算法题，接下来，我计划(在我的能力范围内)写一些常见面试题及其解决思路，希望可以巩固自己的知识，如果可以顺便帮助到一些朋友，就更好不过了。

第一道(也是最简单的一道)面试题便是：如何确定一个字符串中是否所有字符全部互不相同？

在开始完成这道题之前，最好先向出题者确认的一件事情是，这是字符串是纯ASCII字符串还是Unicode字符串。这决定了你后续的解题过程，这个问题可以向面试官传达出你很关注细节，且对计算机科学有一定认识。

这里假设字符集为ASCII，当然如果是Unicode，只需要扩大内存，其他解题思路上基本是一致的。

首先需要想到的是，ASCII只有一个字节，意味着如果待检测的字符串长度超过了256位，那么这个字符串中一定有重复的元素。解题的方式有很多种，下面列举几种常见的解法：

---

最简单的解法是将字符串中的每一个字符与剩下的字符比较，如果遇到相同的元素，则返回False，如果直到遍历结束都没有遇到相同元素，则返回True：

def is_unique_char(string):
    str_len = len(string)
    
    if str_len > 256:
        return True
    
    for pos in xrange(str_len):
        for index in xrange(pos+1, str_len):
            if string[pos] == string[index]:
                return False
    
    return True

这种解法的时间复杂度为O(n*n)，空间复杂度为O(1)。当然很明显，这种解法的效率非常低下，有什么更好的实现呢？

第二种解法是通过构建一个布尔值的数组，索引index表示ASCII码中值为index的字符。将初值置为False，如果某个元素第二次出现，则表示这个字符串出现了重复的字符，函数直接返回。这种解法的Python实现如下：

def is_unique_char(string):
    if len(string) > 256:
        return True
    
    record = [False] * 256
    
    for ch in string:
        ch_val = ord(ch)
        
        if record[ch_val]:
            return False
        
        record[ch_val] = True
    
    return True

上面代码的时间复杂度为O(n)，空间复杂度为O(1)。不过，我们可以非常确定的是，n的最大值仅仅为256。

---

如果使用位运算，结合Python中数字的特殊实现，我们仅需要一个数字来替代record即可实现上面的算法：

def is_unique_char(string):
    if len(string) > 256:
        return True
    
    record = 0L
    
    for ch in string:
        print record
        ch_val = ord(ch)
        
        if (record & (1 << ch_val)) > 0:
            return False
        
        record |= (1 << ch_val)
    
    return True

---

如果允许对字符串进行修改，则我们还有一种O(nlog(n))的算法来解决这个问题：将字符串排序，然后遍历每一个元素并与周围元素比较(请自行尝试)。

---

如果考虑到Python的某些数据结构，则我们可以通过collections里的工具来实现：

from collections import Counter

is_unique_char = lambda s: True if len(s) > 256 else not bool(filter(lambda n: n > 1, Counter(s).values()))

---

这些算法可能算不上最优解，不过根据题目，我们依次从比较容易的实现向比较复杂的实现再结合Python的集合类，让出题者了解了你的思考过程和对特定语言的工具集的使用。

这应该是面试中最最简单的算法题目了，接下来我打算(在我的能力范围里)再由浅入深多写点。

打赏支持我写出更多好文章，谢谢！

打赏作者

打赏支持我写出更多好文章，谢谢！