01.01. Is Unique

Description

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Example 1:


Input:  = "leetcode"

Output: false

Example 2:


Input: s = "abc"

Output: true

Note:

0 <= len(s) <= 100

Solutions

Solution 1: Bit Manipulation

Based on the examples, we can assume that the string only contains lowercase letters (which is confirmed by actual verification).

Therefore, we can use each bit of a \(32\)-bit integer mask to represent whether each character in the string has appeared.

The time complexity is \(O(n)\), where \(n\) is the length of the string. The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptJavaScriptSwift

class Solution:
    def isUnique(self, astr: str) -> bool:
        mask = 0
        for i in map(lambda c: ord(c) - ord("a"), astr):
            if (mask >> i) & 1:
                return False
            mask |= 1 << i
        return True

class Solution {
    public boolean isUnique(String astr) {
        int mask = 0;
        for (char c : astr.toCharArray()) {
            int i = c - 'a';
            if (((mask >> i) & 1) == 1) {
                return false;
            }
            mask |= 1 << i;
        }
        return true;
    }
}

class Solution {
public:
    bool isUnique(string astr) {
        int mask = 0;
        for (char c : astr) {
            int i = c - 'a';
            if (mask >> i & 1) {
                return false;
            }
            mask |= 1 << i;
        }
        return true;
    }
};

func isUnique(astr string) bool {
    mask := 0
    for _, c := range astr {
        i := c - 'a'
        if mask>>i&1 == 1 {
            return false
        }
        mask |= 1 << i
    }
    return true
}

function isUnique(astr: string): boolean {
    let mask = 0;
    for (let j = 0; j < astr.length; ++j) {
        const i = astr.charCodeAt(j) - 'a'.charCodeAt(0);
        if ((mask >> i) & 1) {
            return false;
        }
        mask |= 1 << i;
    }
    return true;
}

/**
 * @param {string} astr
 * @return {boolean}
 */
var isUnique = function (astr) {
    let mask = 0;
    for (const c of astr) {
        const i = c.charCodeAt() - 'a'.charCodeAt();
        if ((mask >> i) & 1) {
            return false;
        }
        mask |= 1 << i;
    }
    return true;
};

class Solution {
    func isUnique(_ astr: String) -> Bool {
        var mask = 0
        for c in astr {
            let i = Int(c.asciiValue! - Character("a").asciiValue!)
            if (mask >> i) & 1 != 0 {
                return false
            }
            mask |= 1 << i
        }
        return true
    }
}

01.01. Is Unique

Description

Solutions

Solution 1: Bit Manipulation

Comments