剑指offer32：有效的变位词

本文主要是介绍剑指offer32：有效的变位词，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：
给定两个字符串s和t，请判断它们是不是一组变位词。在一组变位词中，它们的字符以及每个字符出现的次数都相同，但字符的顺序不能相同。例如，“anagram”和“nagaram”就是一组变位词。
分析：
如果只考虑英文小写字母，那就可以利用数组模拟哈希表，创建一个容量为26个英文字母大小的数组来存储每个字母出现的次数，先将第一组字符串按照对应位置分别将出现的次数存储在容量26的数组中，然后将第二组字符串按照自己在数组的对应位置减1，如果数组都为0相当于抵消了就一定是一组变位词，为了再加快程序，可以直接判断第二组字符在数组中对应的值是否为0，如果为0，则说明第二组字符串中的这个字符不存在第一组字符串中或这个字符出现的次数比第一组中的这个字符的次数少。
什么都考虑就直接利用HashMap就可以了，也是字符对应出现次数，思路和上一段类似。
代码：

import java.util.HashMap;
import java.util.Map;

public class IsAnagram {
    //    如果只考虑英文小写字母的话
    public static boolean isAnagram1(String str1, String str2) {
        if (str1.length() != str2.length()) {
            return false;
        }
        int[] ints = new int[26];
        for (char ch : str1.toCharArray()) {
            ints[ch - 'a']++;
        }
        for (char ch : str2.toCharArray()) {
            if (ints[ch - 'a'] == 0) {
                return false;
            }
            ints[ch - 'a']--;
        }
        return true;
    }

    //    如果考虑非英文字母，ASCII码字符的长度为8位，所以ASCII码字符集能只能包含256个不同的字符，中文以及很多语言的
//    的字符集都远远超过这个数字。unicode一共16位，包含65535个字符。但用它又有些浪费内存，可以采用HashMap
    public static boolean isAnagram2(String str1, String str2) {
        if (str1.length() != str2.length()) {
            return false;
        }
        Map<Character, Integer> counts = new HashMap<>();
        for (char ch : str1.toCharArray()) {
//            getOrDefault方法获取ch对应的值，如果获取不到。默认值为0
//            哈希表keys是字母和values是出现的次数
            counts.put(ch, counts.getOrDefault(ch, 0) + 1);
        }
        for (char ch : str2.toCharArray()) {
            if (!counts.containsKey(ch) || counts.get(ch) == 0) {
                return false;
            }
            counts.put(ch, counts.get(ch) - 1);
        }
        return true;
    }
}

这篇关于剑指offer32：有效的变位词的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！