Java 中的变位词（Anagram）处理

简介

在 Java 编程中，变位词（Anagram）是一个常见的概念。变位词指的是由相同字母重排列形成的单词（或短语），比如 “listen” 和 “silent” 就是一对变位词。在实际开发中，判断两个字符串是否为变位词是一个常见的需求，例如在文本处理、密码学等领域都有应用。本文将详细介绍 Java 中变位词的基础概念、使用方法、常见实践以及最佳实践。

基础概念

变位词的定义

变位词是指由相同字母组成，但字母排列顺序不同的单词或短语。例如，“triangle” 和 “integral” 是变位词，因为它们都由字母 'a', 'e', 'g', 'i', 'l', 'n', 'r' 组成。

Java 中的变位词判断原理

判断两个字符串是否为变位词的核心思路是比较它们包含的字母及其出现的次数是否相同。可以通过统计每个字符串中字母的出现次数，然后比较这些统计结果来实现。

使用方法

方法一：排序法

排序法的基本思路是将两个字符串按字母顺序排序，然后比较排序后的字符串是否相等。如果相等，则它们是变位词。

import java.util.Arrays;

public class AnagramChecker {
    public static boolean isAnagram(String str1, String str2) {
        // 首先检查两个字符串是否为 null 或长度是否不同
        if (str1 == null || str2 == null || str1.length() != str2.length()) {
            return false;
        }
        // 将字符串转换为字符数组
        char[] charArray1 = str1.toCharArray();
        char[] charArray2 = str2.toCharArray();
        // 对字符数组进行排序
        Arrays.sort(charArray1);
        Arrays.sort(charArray2);
        // 比较排序后的字符数组
        return Arrays.equals(charArray1, charArray2);
    }

    public static void main(String[] args) {
        String str1 = "listen";
        String str2 = "silent";
        System.out.println(isAnagram(str1, str2)); // 输出: true
    }
}

方法二：计数法

计数法的思路是使用一个数组来统计每个字符的出现次数。对于第一个字符串，增加对应字符的计数；对于第二个字符串，减少对应字符的计数。最后检查数组中的所有元素是否都为 0。

public class AnagramChecker {
    public static boolean isAnagram(String str1, String str2) {
        // 首先检查两个字符串是否为 null 或长度是否不同
        if (str1 == null || str2 == null || str1.length() != str2.length()) {
            return false;
        }
        // 假设字符串只包含小写字母
        int[] charCount = new int[26];
        // 统计第一个字符串中每个字符的出现次数
        for (char c : str1.toCharArray()) {
            charCount[c - 'a']++;
        }
        // 减少第二个字符串中每个字符的计数
        for (char c : str2.toCharArray()) {
            charCount[c - 'a']--;
            // 如果某个字符的计数小于 0，说明不是变位词
            if (charCount[c - 'a'] < 0) {
                return false;
            }
        }
        // 检查数组中的所有元素是否都为 0
        for (int count : charCount) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String str1 = "listen";
        String str2 = "silent";
        System.out.println(isAnagram(str1, str2)); // 输出: true
    }
}

常见实践

变位词分组

在实际应用中，可能需要将一组字符串按变位词进行分组。可以使用哈希表来实现这个功能。

import java.util.*;

public class AnagramGrouper {
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> anagramMap = new HashMap<>();
        for (String str : strs) {
            // 将字符串按字母顺序排序
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sortedStr = new String(charArray);
            // 如果排序后的字符串不在哈希表中，创建一个新的列表
            if (!anagramMap.containsKey(sortedStr)) {
                anagramMap.put(sortedStr, new ArrayList<>());
            }
            // 将原字符串添加到对应的列表中
            anagramMap.get(sortedStr).add(str);
        }
        // 将哈希表中的所有列表添加到结果列表中
        return new ArrayList<>(anagramMap.values());
    }

    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> result = groupAnagrams(strs);
        for (List<String> group : result) {
            System.out.println(group);
        }
    }
}

最佳实践

性能考虑

排序法：时间复杂度为 $O(n log n)$，其中 $n$ 是字符串的长度。因为排序操作的时间复杂度是 $O(n log n)$。
计数法：时间复杂度为 $O(n)$，因为只需要遍历字符串一次。因此，在处理大规模数据时，计数法的性能更好。

代码可读性和可维护性

使用有意义的变量名和注释，提高代码的可读性。
将不同的功能封装成独立的方法，提高代码的可维护性。

小结

本文介绍了 Java 中变位词的基础概念、使用方法、常见实践以及最佳实践。通过排序法和计数法可以判断两个字符串是否为变位词，其中计数法的性能更好。在实际应用中，可以使用哈希表将一组字符串按变位词进行分组。在编写代码时，应考虑性能、可读性和可维护性。

参考资料

《Effective Java》
Java 官方文档
LeetCode 相关题目