哈希表系列① -- 有效的字母异位词

举报
十八岁讨厌编程 发表于 2022/08/06 01:07:44 2022/08/06
【摘要】 文章目录 题目概述解题思路代码实现小总结 题目概述 此题对应力扣的242.有效的字母异位词 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 注意:...

题目概述

此题对应力扣的242.有效的字母异位词

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。
示例:
输入: s = “anagram”, t = “nagaram”
输出: true
输入: s = “rat”, t = “car”
输出: false

解题思路

哈希表有三种抽象的实现方式:

  • 数组
  • 集(Set)
  • 映射(Map)

对于这种对比字母串(仅由英文字符组成的字符串)的题目,我们可以利用其26个字母(大写、小写)的ASCII值是连在一起的特性,将a / A 作为一个基准进行计数。对此我们可以选择用数组这个结构。

我们创建一个26长度的数组之后,将第一个字符串的每一个字符单独拿出来,与a / A 的ASCII值进行相减,相减得到的数字作为在数组中存储的索引。如此进行下去,将第一个字符串处理完之后,数组中就存储了每个字母出现的次数。

同理,将第二个字符串也这么处理,不过是在原数组的数据上进行减法操作。处理完之后最后得到的数组,如果每一个数据都为0,则说明是有效的字母异位词,反之,则不是。

代码实现

class Solution {
    public boolean isAnagram(String a, String b) {
        int[] box = new int[26];
		for(char jia : a.toCharArray()) {
			box[jia - 'a'] += 1;
		}
		for(char jian : b.toCharArray()) {
			box[jian - 'a'] -= 1;
		}
		for(int num : box) {
			if (num != 0)return false;	 
		}
		return true;
    }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

可以对代码进行修剪:

class Solution {
    public boolean isAnagram(String a, String b) {
        int[] box = new int[26];
		for(char jia : a.toCharArray())  box[jia - 'a'] += 1;
		for(char jian : b.toCharArray()) box[jian - 'a'] -= 1;
		for(int num : box) if (num != 0) return false;	 
		return true;
    }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

小总结

如果涉及到26个字母的存储计数的时候,利用数组是一个更加高效的选择。

文章来源: blog.csdn.net,作者:十八岁讨厌编程,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/zyb18507175502/article/details/123306742

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。