242.有效的字母异位词

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

示例 1:

输入: s = "anagram", t = "nagaram" 输出: true 示例 2:

输入: s = "rat", t = "car" 输出: false 说明: 你可以假设字符串只包含小写字母。

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

本质

两个字符串中，每个字母出现的次数是完全一致的

• 因此，长度不一致一定不是异位词

哈希表法

• 字母作为 key，出现次数作为 value
• 针对两个词，构建两个 HashMap 进行比较

优化——数组法

题目说了 key 只会是 26 个小写字母，那么可以构建一个长度 26 的整形数组，index = 0 位置就表示 a 出现的次数，以此类推

• 索引位置 = 当前字符 - 97 （a 的 ASCII 码）
• 可以写为 char - 'a'

构建两个数组然后比较

public boolean isAnagram(String s, String t) {

if (s.length() != t.length()) return false;

// 长度一致

int[] countsS = getCountsArray(s);

int[] countsT = getCountsArray(t);

for (int i = 0; i < countsS.length; i++)

if (countsS[i] != countsT[i]) return false;

return true;

}

private int[] getCountsArray(String s) {

int[] counts = new int[26];

for (int i = 0; i < s.length(); i++)

counts[s.charAt(i) - 'a']++;

return counts;

}

只构建一个数组

对第一个字符串构建数组，在遍历第二字符串时，在字符对应位置上 -1

• 减完以后如果数组有位置上的值 < 0，说明第二个词中某字母比第一个词多，就不是异位词，

public boolean isAnagram(String s, String t) {

char[] charS = s.toCharArray();

char[] charT = t.toCharArray();

if (charS.length != charT.length) return false;

// 长度一致

int[] counts = new int[26];

for (char c : charS) counts[c - 'a']++;

for (char c : charT)

if (--counts[c - 'a'] < 0)

return false;

return true;

}