- 前言
- 题目
- 题解
- NO1：暴力法（O(n^2^)，超时）
- NO2：哈希法（重点，O(n)）
- NO3：借助Java的API来解决
- 参考文章
哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。
这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。
目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为哈希表专题。
题目
题目来源leetcode
leetcode地址：242. 有效的字母异位词，难度：简单。
题目描述(摘自leetcode)：
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。 示例 1: 输入: s = "anagram", t = "nagaram" 输出: true 示例 2: 输入: s = "rat", t = "car" 输出: false 提示: 1 <= s.length, t.length <= 5 * 104 s 和 t 仅包含小写字母
本地调试代码：
class Solution {
public boolean isAnagram(String s, String t) {
...
}
public static void main(String[] args) {
String s = "anagram";
String t = "anggram";
System.out.println(new Solution().isAnagram(s,t));
}
}
题解 NO1：暴力法（O(n2)，超时）
思路：
代码：
public boolean isAnagram(String s, String t) {
//字符串长度不相等、为0情况直接返回
if(s == null || t == null || s.length() != t.length() || s.length() == 0){
return false;
}
for (int i = 0; i < s.length(); i++) {
int sNum = 0;
char sChar = s.charAt(i);
//s字符串获取当前字符的相同个数
for (int j = 0; j < s.length(); j++) {
if(sChar == s.charAt(j)){
sNum++;
}
}
//t字符串统计sChar的个数
int tNum = 0;
for (int j = 0; j < t.length(); j++) {
if(sChar == t.charAt(j)){
tNum++;
}
}
if(tNum !=sNum){
return false;
}
}
return true;
}
NO2：哈希法（重点，O(n)）
思路：根据提示s 和 t 仅包含小写字母，所以我们可以直接定义一个大小为26的int数组默认索引值都为0，对应下标0-25存放'a'-'z'的重复次数，之后遍历s、t来进行统计，最终可根据数组中的值是否相等或为0来确定是否为有效的字母异位词。
代码：下面是进行修改了三次，思路都是一致的
//首次看思路自己写代码
public boolean isAnagram(String s, String t) {
if(s == null || t == null || s.length()!=t.length() || s.length() == 0){
return false;
}
//设置两个数组来进行分别记录对应的字符串字符的数量
int[] sArr = new int[26];
int[] tArr = new int[26];
//遍历一遍s
for (int i = 0; i < s.length(); i++) {
sArr[s.charAt(i)-'a']++;
tArr[t.charAt(i)-'a']++;
}
for (int i = 0; i < 26; i++) {
if(sArr[i] != tArr[i]){
return false;
}
}
return true;
}
//优化一：两个数组=>一个数组
public boolean isAnagram(String s, String t) {
if(s == null || t == null || s.length()!=t.length() || s.length() == 0){
return false;
}
//使用一个数组来进行存储
int[] recordsNumsArr = new int[26];
//长度一致，我们分别来进行+、-操作对数组的某个索引值
for (int i = 0; i < s.length(); i++) {
recordsNumsArr[s.charAt(i)-'a']++;
recordsNumsArr[t.charAt(i)-'a']--;
}
//来对记录字符数的数组进行遍历，一旦某个数组索引值!=0说明不有效
for (int i = 0; i < 26; i++) {
if(recordsNumsArr[i] != 0){
return false;
}
}
return true;
}
//优化二：添加提前结束操作
public boolean isAnagram(String s, String t) {
if(s == null || t == null || s.length()!=t.length() || s.length() == 0){
return false;
}
//使用一个数组来进行存储
int[] recordsNumsArr = new int[26];
for (int i = 0; i < s.length(); i++) {
recordsNumsArr[s.charAt(i)-'a']++;
}
for (int i = 0; i < t.length(); i++) {
recordsNumsArr[t.charAt(i)-'a']--;
//提前结束：一旦在t中的某个字符相同数量>s中的
if(recordsNumsArr[t.charAt(i)-'a'] < 0){
return false;
}
}
//来对记录字符数的数组进行遍历，一旦某个数组索引值!=0说明不有效
for (int i = 0; i < 26; i++) {
if(recordsNumsArr[i] != 0){
return false;
}
}
return true;
}
用Java执行的话大多数都是需要4ms，我还在想为啥只击败了45%，之后使用c语言的同样逻辑代码测了下过0ms，直接击败100%。
bool isAnagram(char *s, char *t)
{
int i, x[26] = { 0 }, y[26] = { 0 };
for (i = 0; s[i] != ' '; i++) x[s[i] - 'a']++; //建立 s 的字符表 x
for (i = 0; t[i] != ' '; i++) y[t[i] - 'a']++; //建立 t 的字符表 y
for (i = 0; i < 26; i++) //比较两字符表是否相同
if (x[i] != y[i]) return false;
return true; //种类、个数均相同
}
NO3：借助Java的API来解决
//方式一：字符数组排序比对
public boolean isAnagram(String s, String t) {
if(s == null || t == null || s.length()!=t.length() || s.length() == 0){
return false;
}
//思路：字符串s、t转成字符数组，分别进行排序，之后使用Arrays工具类进行比较
char[] sArr = s.toCharArray();
char[] tArr = t.toCharArray();
Arrays.sort(sArr);
Arrays.sort(tArr);
return Arrays.equals(sArr,tArr);
}
//方式二：利用map集合解决
public boolean isAnagram(String s, String t) {
if(s == null || t == null || s.length()!=t.length() || s.length() == 0){
return false;
}
Map map = new HashMap<>(s.length());
//遍历字符数组s，以key、value进行存储，key设置为字符，value则表示指定的数字
for(char ch : s.toCharArray()){
map.put(ch,map.getOrDefault(ch,0)+1);
}
//遍历字符数组t
for(char ch : t.toCharArray()){
Integer num = map.get(ch);
//为null表示没有该数
if(num == null){
return false;
}else if(num>1){
map.put(ch,num-1);
}else{ //num<=1情况，数量-1即可0，此时我们直接移除即可
map.remove(ch);
}
}
return map.isEmpty();
}
//方式三：使用strean
public boolean isAnagram(String s, String t) {
if(s == null || t == null || s.length()!=t.length() || s.length() == 0){
return false;
}
int[] numArr = new int[26];
//这里不使用stream是因为若是转为数组还有个copy过程
s.chars().forEach(ch->numArr[ch-'a']++);
t.chars().forEach(ch->numArr[ch-'a']--);
//直接对数组进行stream流操作
return Arrays.stream(numArr).allMatch(ch->ch == 0);
}
参考文章
[1]. leetcode题解
[2]. 代码随想录—242.有效的字母异位词
我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！
欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料
Q群：851968786 我们可以一起探讨学习
注明：转载可，需要附带上文章链接
