Leetcode刷题-242：有效的字母异位词

1.题目描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例1：

输入: s = “anagram”, t = “nagaram”
输出: true

示例2：

输入: s = “rat”, t = “car”
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-anagram

2.题目分析

2.1 哈希集合解法

• 直接解题的话，得出题目中首当其冲我们要求的就是两个字符串中每个字母出现的次数，然后对齐进行比较。解法这不就来了，我们学过的一种数据结构不就是为了这种映射而生的吗。于是决定选择undered_set来解决题目。
• 但是继续思考一下，本题中的字母一共也就26个，采用set来实现的话如果有一个字母出现的次数较多，二者进行比较时总是有点麻烦。举个栗子，如果是字符串abab和字符串baba比较的话，我们采用set的话只能二者全部统计完成后再进行set的比较，我们不能使用一个set来进行实现。（这里使用set的删除操作比较麻烦）。
• 题目中出现的字母一共只有26个而且set本身也就是一个数组，所以我们直接采用映射26个字母的int数组record来进行解题，每个下标位置的int数组保存相应字母出现的次数，如record[0]就表示a出现的次数，record[3]就表示d出现的次数。这样我们就可以总结出下面的解题步骤：

1. 初始化record数组的元素全为0 ；
2. 首先遍历s字符串，每当遍历到一个字母就将其相应位置的int数组值+1，直到字符串遍历完
3. 然后遍历t字符串，每当遍历到一个字母就将其相应位置的int数组值-1，直到字符串遍历完
4. 最后判断record数组中的元素是否全为0，若是则两个字符串是字母异位词，否则不是。

2.2 字符串排序解法

• 我们进一步来分析题目，考虑到题目中的要求是每个字母的出现次数相等，也就是说两个字符串不一定是相等的，但是字母的组成是相同的。举个例子一个字符串是abc，另一个是cba，它们此时是字母异位词。那么我们就可以想到，如果对两个字符串排序的画，那是字母异位词的两个字符串是不是就相等了呢。事实就是这样的。所以我们可以利用这种方法来进行解题。

  具体步骤就是，首先分别对两个字符串排序，然后看二者是否相等，若相等则为字母异位词，否则就不是。具体代码见3.2.

3.题目解答

3.1 类哈希存储

class Solution {
public:
    bool isAnagram(string s, string t) {
    	//设置一个数组保存每个字母出现的次数
        int record[26]{0};
        //遍历s字符串进行出现次数统计
        for(char c:s){
            record[c-'a']++;
        }
        //遍历s字符串进行出现次数统计
        for(char c:t){
            record[c-'a']--;
        }
        //因为两个串的字符出现次数统计是正负相反
        //所以当某个字母的最后统计为0则说明该字母满足条件。
        for(auto c:record){
            if(c != 0)
                return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.2 排序判相等

bool isAnagram(string s, string t) {
		//长度不想等则必然不是字母异位词
        if(s.length() != t.length()){
            return false;
        }
        //分别进行排序
        sort(s.begin(),s.end());
        sort(t.begin(),t.end());
        return s==t;
    }
1
2
3
4
5
6
7
8
9
10