LeetCode：判定字符是否唯一

比眉伴天荒 2022-11-21 03:35 130阅读 0赞

![在这里插入图片描述][20201026133356480.png_pic_center]

题目：

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

示例 1：

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

示例 2：

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

> 限制：  
> 0 <= len(s) <= 100  
> 如果你不使用额外的数据结构，会很加分。  
> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/is-unique-lcci  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

> 思路：  
> 当然先来暴力破解它，就是两个for循环比较如果有相等的，就直接返回false，当然我们一定要把边界值给考虑上，这个细节一定要注意：  
> 第一种方式：

if (astr.length() == 0 || astr.length() == 1){ 
                return true;
            }
            for (int i = 0; i < astr.length(); i++) { 
                for (int j = i+1; j < astr.length(); j++) { 
                    if (astr.charAt(i) == astr.charAt(j)){ 
                        return false;
                    }
                }
            }
            return true;

时间复杂度为：O(n\*n)

> 可看这样的时间复杂度还是太大了，如果遇到最坏的情况下，就直接变成 了n\*n的形式，效率太低了：  
> 下面我们采用哈希表降低时间复杂度：

思路：

> 我们先将26个英文字母放入到哈希表中，并给每个字母都赋值为0，然后再迭代这个字符串，然后与哈希表中的字符比较，如果相同就将值+1并将原来的给替换，在这里我们一定要判断如果哈希表中的某个字母的值为2时，就可以直接返回false，不用再比较了，这里要注意！

第二种方式：

public static boolean isUnique2(String astr) { 
            if (astr.length() == 0 || astr.length() == 1 || astr.equals("")){ 
                return true;
            }
            HashMap<Character, Integer> map = new HashMap<>();
    
            for (int i = 97; i <= 122; i++) { 
                map.put((char)i, 0);
            }
            for (int i = 97,j = 0; i <= 122; i++,j++) { 
                if (j < astr.length() && map.containsKey(astr.charAt(j))) { 
                    System.out.println(astr.charAt(j) + "---" + ((map.get(astr.charAt(j))) + 1));
                    map.put(astr.charAt(j), map.get(astr.charAt(j)) + 1);
                    if (map.get(astr.charAt(j)) >= 2){ 
                        return false;
                    }
                }
            }
    // for (Map.Entry<Character, Integer> entry : map.entrySet()) { 
    // if (entry.getValue() >= 2){ 
    // return false;
    // }
    // }
            System.out.println(map);
            return true;
        }

时间复杂度为：O(n)  
这样就把时间复杂度将到n！

如果有什么问题，请大家不吝赐教！

[20201026133356480.png_pic_center]: /images/20221120/37e4c9916f5d4ceaaf67942220c130cb.png