【Java题解】面试题 01.01. 判定字符是否唯一

【Java题解】面试题 01.01. 判定字符是否唯一

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

输入: s = “leetcode”
输出: false

示例 2：

输入: s = “abc”
输出: true

限制：

0 <= len(s) <= 100

如果你不使用额外的数据结构，会很加分。

方法一：
使用set或者map，进行一次遍历即可。

代码：

class Solution {
    public boolean isUnique(String astr) {
        // map set
        Set set = new HashSet<>();
        for (int i = 0; i < astr.length(); i++) {
            char c = astr.charAt(i);
            if (set.contains(c)) return false;
            else set.add(c);
        }
        return true;
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

方法二：
使用char数组，先排序，然后遍历判断前后元素是否相等。

class Solution {
    public boolean isUnique(String astr) {
        char[] arr = astr.toCharArray();
        Arrays.sort(arr);
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == arr[i - 1]) return false;
        }
        return true;
    }
}

时间复杂度：O(nlgn)
空间复杂度：O(n)

方法三：
不适用额外的数据结构，用位运算。
a : a - ‘a’ = 0
b : b - ‘a’ = 1
…
那么让1 << 0, 1 << 1，对应的二进制为：1 10 这样就能利用二进制中的1的位置来区分不同的字母。
如果现在的二进制 & (1 << 一个字母 - 'a’得到的数) == 1 那就说明已经存在这个字母了，return false; 如果 ==0，那么就让现在的二进制对应的位置，置为1，通过 | 就可以了。

代码：

class Solution {
    public boolean isUnique(String astr) {
        // 不使用额外的数据结构
        int mark = 0;
        for (int i = 0; i < astr.length(); i++) {
            int moveBit = astr.charAt(i) - 'a';
            if ((mark & (1 << moveBit)) != 0) return false;
            mark |= 1 << moveBit;
        }
        return true;
    }
}