Question

面试题 01.01. 判定字符是否唯一

English Version

题目描述

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

示例 1：

输入: s = "leetcode"
输出: false 

示例 2：

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

限制：

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

解法

方法一：位运算

根据示例，可以假定字符串中只包含小写字母（实际验证，也符合假设）。

因此，我们可以使用一个 $32$ 位整数 mask 的每一位来表示字符串中的每一个字符是否出现过。

时间复杂度 $O(n)$，其中 $n$ 为字符串长度。空间复杂度 $O(1)$。

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

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;
};