0 题目来源

力扣《程序员面试金典》

1 本题涉及到的知识点

字符串、哈希、排序

2 题目描述

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

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

    3 输入与输出格式

    无，力扣略了

    4 样例

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

    5 分析与代码

    方法1 哈希表法

    本题要求判断所有字符是否都不同，可以猜测字符的范围为26个小写字母，因此可以用26个大小的哈希表来判断。过程为：对字符串进行遍历，再此过程中，每出现一次相应字符，就在哈希表中的对应位置加一。最终判断哈希表中是否有超过1的表项，若有，则说明出现了相同的字符。
    因为本题要求最好不要使用额外的数据结构，因此本方法不是最佳方案。
    源代码：
    1. class Solution {
    2. public:
    3.   int table[26]={0};
    4.   bool isUnique(string astr) {
    5.       for(int i=0;i<astr.size();i++)
    6.           table[astr[i]-'a']++;//遍历字符串
    7.       for(int i=0;i<26;i++)//遍历哈希表
    8.       {
    9.           if(table[i]>1)
    10.               return false;
    11.       }
    12.       return true;
    13.   }
    14. };

    方法2 排序法

    为了不使用额外的数据结构，我们可以先对给定的字符串进行排序，然后对字符串进行遍历，如果发现字符串有相邻两个字符相等，则输出false。这种方法没有使用额外的数据结构，适用于更大的字符范围。
    代码：
    1. #include<algorithm>
    2. class Solution {
    3. public:
    4.   bool isUnique(string astr) {
    5.       if(astr=="")
    6.           return true;
    7.       sort(astr.begin(),astr.end());//排序
    8.       for(int i=0;i<astr.size()-1;i++)//遍历字符串
    9.       {
    10.           if(astr[i]==astr[i+1])//相邻两项比较
    11.               return false;
    12.       }
    13.       return true;
    14.   }
    15. };

    其他解法

    位运算解法之后补充
    力扣大佬的评论：
    image.png