LeetCode題目笔记——面试题 01.01. 判定字符是否唯一

文章目录

• • 题目描述
  • 题目难度——简单
  • 方法一：使用集合
  • • 代码/Python
  • 方法二——用一个数组
  • • 代码/Python
  • 方法三——位运算
  • • 代码/Python
  • 总结

题目描述

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

示例 1：

输入: s = “leetcode”
输出: false
示例 2：

输入: s = “abc”
输出: true
限制：

0 <= len(s) <= 100
s[i]仅包含小写字母
如果你不使用额外的数据结构，会很加分。

题目难度——简单 方法一：使用集合

  题目说判断字符是否唯一，回想一下我们常用的数据结构，集合里的元素就是唯一的，所以我们就可以将这个字符串转换成字典，然后判断转换后的字典长度和原字符串的长度是否一样就可以了。

代码/Python

class Solution:
    def isUnique(self, astr: str) -> bool:
        # 方法二，直接用额外的集合结构
        return len(set(astr)) == len(astr) 

有点慢，而且题目也说了不使用额外的数据结构会很加分，所以考虑优化。

方法二——用一个数组

  题目说了只有小写字母出现，那么建一个长度为26的数组，记录字符的出现次数不就好了，遍历一次字符串，把当前字符x和‘a’的距离作为下标，访问这个数组，如果是1说明已经出现过，返回false，否则将该位置为1.

代码/Python

class Solution:
    def isUnique(self, astr: str) -> bool:
        # 方法一，用一个数组标记26个小写字母的出现次数
        occurs = [0] * 26
        head = ord('a')
        for a in astr:
            idx = ord(a) - head
            if occurs[idx] == 1:
                return False
            else:
                occurs[idx] = 1
        
        return True

方法三——位运算

  位运算其实整体思路也是跟方法二一样，都是记录字符的出现次数，在方法二中用了一个数组来存储出现情况，只有26个字母，那我们就可以用一个4字节的int类型数来表示，32位也够存了，从低位到高位，依次表示26个字母的次数，我们可以通过位运算来将每对应位置一。

代码/Python

class Solution:
    def isUnique(self, astr: str) -> bool:
        # 方法三，位运算，题目说了只包含小写字母，所以可以用一个32位的int数表示每个字母出现次数
        occupy = 0
        head = ord('a')
        for a in astr:
            pos = ord(a) - head
            if (occupy & (1 << pos)) != 0:
                return False
            else:
                occupy |= (1 << pos)
        
        return True    

class Solution {
public:
    bool isUnique(string astr) {
        int n = astr.size(), occupy[26] = {0};
        for(auto a: astr){
            if(occupy[a - 'a'] == 1){
                return false;
            } 
            else{
                occupy[a - 'a'] = 1;
            }
        }
        return true;
    }
};

总结

  三种方法的时间都是O(N)，因为都要遍历一次字符串，前两种空间是O(N)，第三种只用到了一个额外的变量，所以是O(1)，有时候我们可以用一个数字的位表示来进行位运算。