经一个在谷歌实习的朋友的推荐下，从英国亚马逊购入了第六版Cracking the Coding Interview。书中介绍了很多IT面试技巧并有189个编程问题。虽然我自己并没有在准备面试，但是打算每天看一题锻炼一下。由于这本书非常流行，网上资料比较多，并且有中文版——《程序员面试金典》(第五版)，记录下来的主要目的是加深自己对问题的理解

今天看了题目1.1，由于是第一道题，难度比较小，题目如下：

Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?

问题是判断一个字符串中是否所有字母均不重复，然后再考虑如果不能使用外部数据结构怎么办。其中容易忽视的细节是字符集的范围，例如是ASCII还是Unicode。如果字符串长度大于字符集可表示字符的总数那么一定会有重复。书中给出的答案之一是使用一个包含所有可能出现的字符的布尔值数组，并初始化为false。例如如果字符集为ASCII字符串，则初始化一个128长度的数组，然后历遍需要判定的字符串，当第二次查询到同一个字符时则字符串包含重复字符。这种方法理论上时间复杂度为O(n)，空间复杂度为O(1)。但是当字符集范围较大时，如Unicode字符串，则非常不实用了。所以在Java，Python等一些高级语言中可以利用set的概念的实现，如在Python中：

def uniqueString(str_):
    return len(str_)==len(set(str_))

由于set(Java中HashSet)基于HashTable的概念，也可以达到与使用数组同样的复杂度，但是在实际表现和编程实现上都更好和更方便。

如果不可以使用外部的数据结构，则可以对字符串进行in-place的排序再判定，时间复杂度为O(nlogn)。如果不允许对字符串做任何更改，那只能逐个对字符串中字符串进行判断，时间复杂度为O(n²)。Python代码如下：

def uniqueString(str_):
    for char in str_:
        if str_.count(char) > 1:
            return False
    return True