https://leetcode-cn.com/problems/valid-anagram/
https://github.com/YIMEng-0/DataStructure
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
字母异位词的概念:
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。
简单理解就是:两个字符串长度一样,构成字符串的每个字符只是排列的顺序不一样,含有的具体字符以及具体字符的个数是一样的;
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true 示例 2: 输入: s = "rat", t = "car" 输出: false
对于两个字符串里面的每个字符进行排序,然后比较排序后的结果,调用 Arrays.equals() 方法即可;
排序之前需要将字符串转换为 char 数组,这样子才能方便排序;
使用一个记录字符串中字符出现频次
的数组,这个数组大小定义为 26 因为英语中存在 26 个字母,可以统计所有的字母字符串的情况;
对于字符串 s 来讲记录每个字符出现的次数,出现一次,记录频次的数组就会在相应的位置加一
;
对于字符串 t 来讲,记录每个字符出现的次数,出现一次,在记录频次的数字就会在相应的位置减一
;
如果记录频次的数组最终所有的元素都是 0 ,说明两个字符串是满足字母异位词的定义的;
public static boolean isAnagram(String s, String t) { // 比较字符串的长度,长度不一致的话直接返回 false 即可 if (s.length() != t.length()) { return false; } // 转换成为字符数组类型,方便对单个字符数组进行排序,查看里面的元素是否是相同的 char[] str1 = s.toCharArray(); char[] str2 = t.toCharArray(); // 进行排序处理 Arrays.sort(str1); Arrays.sort(str2); // 进行比较即可,调用了 Arrays 里面的比较函数 return Arrays.equals(str1, str2); }
public boolean isAnagram1(String s, String t) { int[] record = new int[26]; char[] str1 = s.toCharArray(); char[] str2 = t.toCharArray(); for (int i = 0; i < str1.length; i++) { record[str1[i] - 'a'] += 1; } for (int i = 0; i < str2.length; i++) { record[str2[i] - 'a'] -= 1; } for (int i = 0; i < record.length; i++) { if (record[i] != 0) { return false; } } return true; }
for (int i = 0; i < str1.length; i++) { record[str1[i] - 'a'] += 1; }
str1 是字符串 s 转换成为 char[] 数组的结果,这样子可以方便使用char[]数组对字符串中的每个字符进行操作;
i < str1.length;
是对于 s 字符串中所有字符出现的总频次;可以对于 s 字符串中每个字符都统计到;
record[str1[i] - 'a'] += 1;
写法
等价于 record[str1[i] - 'a'] ++;
等价于record[str1[i] - 'a'] = record[str1[i] - 'a'] + 1;
不过后者理解起来可能没有前者理解起来方便;
record 是一个 int 数组,目的就是统计 字符串s
以及 字符串t
两个字符串中字符
出现的次数
通过了排序的方式,以及使用记录数组的方式,可以实现字母异位词的判别。使用记录数组的方式,是对于这个问题的一个转换,大的字符串拆解成为小的字符,然后统计字符的个数,当统计字符个数的数组 record 元素都是 0 的时候,满足字母异位词的定义,输出结果为 true;