leetcode-代码随想录-哈希表-有效的字母异位词

题目

题目链接：242. 有效的字母异位词 - 力扣（LeetCode）
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。

输入: s = "anagram", t = "nagaram"
输出: true

输入: s = "rat", t = "car"
输出: false

class Solution {
public:bool isAnagram(string s, string t) {}
};

思路 & 代码

哈希问题常采用的数据结构：

• 数组：用于数值比较小，范围确定的情况；
• set：用于数值比较大、范围不确定的情况；
• map：用于有 key - value的映射关系时；

数组作哈希表

题目分析：判断两个字符串是否由相同的字符串组成。

1. s 和 t 仅包含小写字母 —— 26个；
2. 小写字母的ASCII是连续的；

所以使用数组 即可，大小为26，存放的是从 a 到 z 每个字母出现的频率。

代码实现思路

将字符 映射到数组也就是哈希表的索引下标上。

1. 定义一个数组 record，大小为 26，初始化为 0；用于记录 字符串中 字符出现的次数。
2. 怎么记录呢？
   • 因为 字符 a 到字符 z 的ASCII是连续的数值，在运行中会自动将 'a’转换为ASCII值。
   • 使用 s[i] - 'a' 操作：若s[i] = ‘a’ ，就映射到下标0，若s[i] = ‘b’，映射到下标1，…，若s[i] = ‘z’，映射到下标 25。
3. 遍历字符串 s，使用 record[s[i] - 'a']++记录字符出现的频率
4. 遍历字符串 t，使用 record[t[i] - 'a']--记录字符出现的频率
5. 遍历 record数组，若数组所有元素均为 0， 说明是字母移位词，否则不是。

#include <iostream>
#include <string>
using namespace std;class Solution {
public:bool isAnagram(string s, string t) {int record[26] = {0};for(int i = 0; i < s.size(); i++){record[s[i] - 'a']++;}for(int i = 0; i < t.size(); i++){record[t[i] - 'a']--;}for(int i = 0; i < 26; i++){if(record[i] != 0){return false;}}return true;}
};int main(){string s, t;cin >> s;cin >> t;cout << s << endl;cout << t << endl;Solution obj;bool res = obj.isAnagram(s,t);cout << boolalpha;cout << "res: " << res << endl;}

时间复杂度：O(n)；
空间复杂度：O(1);