面试题 01.01

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

Example 1:

Input: s = "leetcode" Output: false Example 2:

Input: s = "abc" Output: true

Note:

0 <= len(s) <= 100

Solutions

1. bitset

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

1. sort

class Solution {
public:
    bool isUnique(string astr) {
        sort(astr.begin(), astr.end());
        for (int i = 1; i < astr.size(); i++)
            if (astr[i] == astr[i - 1])
                return false;
        return true;
    }
};