Anagram字符串判断

发表于 分类于
学习笔记

判断两个字符串是否是字母异位词

例:

room(房间)–>moor(沼泽)
tea(茶)–>eat(吃)

算法1

1
2
3
4
5
6
7
8
9
10
11
public boolean isAnagram(String s1, String s2) {
    if (s1.length() != s2.length()) {
        return false;
    }
    char[] c1 = s1.toCharArray();
    char[] c2 = s2.toCharArray();

    Arrays.sort(c1);
    Arrays.sort(c2);
    return Arrays.equals(c1, c2);
}

算法2

ASCII码, 当换成更大的字符集, 例如UTF8, 则不太适合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isAnagram(String s1, String s2) {
    if (s1.length() != s2.length()) {
        return false;
    }
    int[] counter = new int[256];
    for (int i = 0; i < s1.length(); i++) {
        counter[s1.charAt(i)]++;
        counter[s2.charAt(i)]--;
    }
    for (int i = 0; i < 256; i++) {
        if (counter[i] != 0) {
            return false;
        }
    }
    return true;
}

算法3

利用MultiSet可以简化计算和比较过程。MultiSet是一个集合，它支持与重复元素无关的顺序相等。例如，多集{a，a，b}和{a，b，a}是相等的。

添加依赖
1
2
3
4
5
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
</dependency>
代码
1
2
3
4
5
6
7
8
9
10
11
12
public boolean isAnagram(String s1, String s2) {
    if (s1.length() != s2.length()) {
        return false;
    }
    Multiset<Character> m1 = HashMultiset.create();
    Multiset<Character> m2 = HashMultiset.create();
    for (int i = 0; i < s1.length(); i++) {
        m1.add(s1.charAt(i));
        m2.add(s2.charAt(i));
    }
    return m1.equals(m2);
}