Unique Characters

Source

• lintcode: Unique Characters

Implement an algorithm to determine if a string has all unique characters.

Example
Given "abc", return true.

Given "aab", return false.

Challenge
What if you can not use additional data structures?

Python

使用hashtable 时间复杂度为O(n), 空间复杂度为O(n)

class Solution:
    # @param s: a string
    # @return: a boolean
    def isUnique(self, str):
        # write your code here
        hash_set = set()

        for s in str:
            if s in hash_set:
                return False
            else:
                hash_set.add(s)
        return True

使用双重循环 时间复杂度为O(n^2), 空间复杂度为O(1)

class Solution:
    # @param s: a string
    # @return: a boolean
    def isUnique(self, str):

        for i in range(len(str)):
            for j in range(i+1, len(str)):
                if str[j]==str[i]:
                    return False
        return True