题目描述
实现一个算法,确定一个字符串 s
的所有字符是否全都不同。
示例 1:
输入: s = "leetcode" 输出: false
示例 2:
输入: s = "abc" 输出: true
限制:
0 <= len(s) <= 100
- 如果你不使用额外的数据结构,会很加分。
解法
方法一:位运算
根据示例,可以假定字符串中只包含小写字母(实际验证,也符合假设)。
因此,我们可以使用一个 \(32\) 位整数 mask
的每一位来表示字符串中的每一个字符是否出现过。
时间复杂度 \(O(n)\),空间复杂度 \(O(1)\)。其中 \(n\) 为字符串长度。
Python3
class Solution:
def isUnique(self, astr: str) -> bool:
mask = 0
for c in astr:
i = ord(c) - ord('a')
if (mask >> i) & 1:
return False
mask |= 1 << i
return True
Java
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;
}
}
C++
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;
}
};
Go
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
}
JavaScript
/**
* @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;
};
TypeScript
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;
}
...
标签:字符,return,string,mask,isUnique,唯一,判定,false,astr
From: https://www.cnblogs.com/mcfon/p/17514146.html