面试题 01.01 判断字符是否唯一

Posted on | In
Words count in article: 542 | Reading time ≈ 2

题目

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

示例 1:

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

示例 2:

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

:

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

解法

解法一：

借助HashSet。将字符串分割为每个字符的字符HashSet，比较HashSet是否合原字符串长度一致即可。

这里需要注意的是，如果字符串为空，应该返回true

JAVA

1
2
3
4
5
6
7
8
9
public boolean isUnique(String astr) {
        if (null == astr || 0 == astr.length()) {
            return true;
        }
        String[] strs = astr.split("");
        List<String> list = Arrays.asList(strs);
        Set<String> set = new HashSet<>(list);
        return set.size() == astr.length();
    }

解法二：

将字符串转换为char数组，排序，遍历判断即可

JAVA

1
2
3
4
5
6
7
8
9
10
public boolean isUnique(String astr) {
        char[] chars = astr.toCharArray();
        Arrays.sort(chars);
        for (int i = 0;i < chars.length - 1;i++) {
            if (chars[i] == chars[i + 1]) {
                return false;
            }
        }
        return true;
    }

解法三：

暴力破解

Java

1
2
3
4
5
6
7
8
9
10
public boolean isUnique(String astr) {
        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;
    }

解法四：

使用字符串的replace方法。遍历字符串astr的每个字符，将其替换为“”，空字符串。然后比较新的字符串和astr的长度差，如果两者差超过1，表示存在一个字符出现次数是超过一次的

Java

1
2
3
4
5
6
7
8
9
10
public boolean isUnique(String astr) {
        for (int i = 0; i < astr.length();i++) {
            String str = astr;
            str = str.replace(String.valueOf(astr.charAt(i)), "");
            if (str.length() != astr.length() - 1) {
                return false;
            }
        }
        return true;
    }

解法五：

使用bitSet

Java

1
2
3
4
5
6
7
8
9
10
public boolean isUnique(String astr) {
  BitSet bitSet = new BitSet();
        for(int i=0;i<astr.length();i++) {
            if(bitSet.get(astr.charAt(i))) {
                return false;
            }
            bitSet.set(astr.charAt(i));
        }
        return true;
}

解法六：

大胆猜测，题目中的字符范围是小写字母a-z。就可以用一个int变量的其中26位保存莫哥字符是否出现过。

Java

1
2
3
4
5
6
7
8
9
10
11
12
public boolean isUnique(String astr) {
        int mark = 0;
        for(char c : astr.toCharArray()) {
            int move_bit = c - 'a';
            if ((mark & (1 << move_bit)) != 0) {
                return false;
            } else {
                mark |= (1 << move_bit);
            }
        }
        return true;
    }
0%