算法:判定字符是否唯一

描述

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

示例 1:

输入: s = "leetcode"
输出: false
示例 2:

输入: s = "abc"
输出: true
限制:

0 <= len(s) <= 100
如果你不使用额外的数据结构,会很加分。

链接:https://leetcode-cn.com/problems/is-unique-lcci

思路

用一个32位整数的各个二进制位代表该位对应的序号是否有字符,例如1表示存在'a'字符,0b10表示存在'b'字符,等等。
这里认为所有字符都是小写英文字符,如果字符范围更大,需要选择位数更多的整数类型或者用别的数据结构,例如数组或哈希表等。

代码

class Solution {
public:
    bool isUnique(string astr) {
        int bits = 0;
        for (int i = 0;i < astr.size();i++) {
            if (bits & (1 << (astr[i]-'a'))) return false;
            else bits |= (1 << (astr[i]-'a'));
        }
        return true;
    }
};

复杂度
时间复杂度:O(n)
空间复杂度:O(1)

上一篇:【Leetcode_easy】762. Prime Number of Set Bits in Binary Representation


下一篇:0x80070422 修复方法