这是悦乐书的第198次更新，第205篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第61题（顺位题号是242）。给定两个字符串s和t，写一个函数来确定t是否是s的anagram。例如：
输入：s =“anagram”，t =“nagaram”
输出：true
输入：s =“rat”，t =“car”
输出：false
注意：您可以假设该字符串仅包含小写字母。
跟进：如果输入包含unicode字符怎么办？ 您如何使您的解决方案适应这种情况？
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
关于题目中anagram的意思，结合给出的两个示例，大意就是两字符串使用的小写字母一样，但是每个字母所处的位置不是全都一样。此解法是将两字符串s、t转换为字符数组，然后将数组排序，最后比较两数组的元素是否相等，这里借助了工具类Arrays。
此解法的时间复杂度是O(nlog(n))，空间复杂度是O(n)。
public boolean isAnagram(String s, String t) {
if (s == null || t == null || s.length() != t.length()) {
return false;
}
char[] ch = s.toCharArray();
char[] ch2 = t.toCharArray();
Arrays.sort(ch);
Arrays.sort(ch2);
return Arrays.equals(ch, ch2);
}
03 第二种解法
题目限制了只有英文小写字母，我们可以定义一个长度只有26的整数数组，对字符串进行遍历，以当前字符减去字符a所表示的整数为索引，找到对应元素，字符串s所在的字符进行自增，字符串t所在的字符进行自减，然后判断数组中的元素，只要任一元素不等于0，则说明s和t不满足anagram的条件。
此解法时间复杂度是O(n)，空间复杂度是O(1)。
public boolean isAnagram2(String s, String t) {
if (s == null || t == null || s.length() != t.length()) {
return false;
}
int[] arr = new int[26];
for (int i=0; i<s.length(); i++) {
arr[s.charAt(i)-'a']++;
arr[t.charAt(i)-'a']--;
}
for(int num : arr) {
if (num != 0) {
return false;
}
}
return true;
}
04 第三种解法
使用HashMap，key为字符串的单个字符，value为此字符出现的次数，这里借助HashMap的getOrDefault方法来实现，如果存在该key，返回对应的value，否则返回默认值。
先将字符串s的每个字符存入HashMap中，然后遍历字符串字符串t，依次获取每一个字符，如果当前字符不在HashMap中存在，直接返回false，然后将字符存进HashMap中，value值减1，如果当前字符的出现次数为0了，将其remove掉，最后判断HashMap是否为空。
此解法因为用到了map.containsKey()方法，所以时间复杂度最好的情况是O(n)，最坏的情况是O(n^2)，空间复杂度是O(n)。
public boolean isAnagram3(String s, String t) {
if (s == null || t == null || s.length() != t.length()) {
return false;
}
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for (int i=0; i<s.length(); i++) {
char ch = s.charAt(i);
map.put(ch, map.getOrDefault(ch, 0)+1);
}
for (int j=0; j<t.length(); j++) {
char ch = t.charAt(j);
if (!map.containsKey(ch)) {
return false;
}
map.put(ch, map.get(ch)-1);
if (map.get(ch) == 0) {
map.remove(ch);
}
}
return map.isEmpty();
}
此解法是可以应对那些带有unicode字符的字符串，当然也可以使用像第二种解法的那样，使用数组，但是数组容量要扩大到256，其他的思路都是一样的。
05 小结
算法专题目前已连续日更超过一个月，算法题文章61+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论