哈希表系列① -- 有效的字母异位词
【摘要】
文章目录
题目概述解题思路代码实现小总结
题目概述
此题对应力扣的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)