leetcode-242-有效的字母异位词

题源

242-有效的字母异位词

题目描述

给定两个字符串 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 仅包含小写字母

思考

思考一 – stl容器的运用 – 字符串排序

我可以将s,t排序
然后
return s==t;
排序的话用sort()函数可以做到

实现思考一代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(),s.end());
        sort(t.begin(),t.end());
        return s==t;
    }
};

sort()排序函数的时间复杂度为O(NlogN)

所以这个算法的时间复杂度也为O(NlogN)

思考二 – 哈希表 – 单数组

由于字符串由字母组成，而且此题只有小写字母，小写字母有且仅有26个，所以我可以用一个包含26个元素的vector容器来存储26个字母的出现次数，在s上出现的加+1,t上出现的-1，如果s，t是有效的字母异位词，最后的vector容器一定是全0。

实现思考二代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        //记录字符串中字母的出现次数
        vector<int> result(26,0);
  		//s[i] - 'a'作为下标，a-z刚好是0-25
        for (int i = 0;i < s.size();i++){
            result[s[i] - 'a']++;
        }
        for (int i = 0;i < t.size();i++){
            result[t[i] - 'a']--;
        }
        //检查vector<int> result(26,0);是否全0
        for (int i = 0;i < 26;i++){
            //只要有一个不是零，则不是s,t字母异位词
            if(result[i]!=0){
                return false;
            }
        }
        //只有全零才返回true
        return true;
    }
};

三个for()循环，每个for()循环的时间复杂度都是O(n),所以最后的时间复杂度也是O(n)
### 代码二优化 – 剪枝
s，t长度不一样自然也不需要判断

if(s.length()!=t.length()){
            return false;
        }

补充：代码二可剪可不剪，影响的只是效率。而下面代码三的剪枝是必要的，因为剩余的代码不具备处理长度不一样的字符串s，t的能力，

代码二最后的代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        //如果s，t的长度不相等自然不可能是有效的字母异位词
        if (s.length() != t.length())   return false;
        //开辟一个包含26个元素的数组，计数s,t中出现的字母的个数，如果每个字母出现的个数相等，则s,t是有效的字母异位词
        vector<int> Count(26,0);
        
        //如何计数是一个问题，char是int，用s[i] - 'a'得到的是从0 - 25的数字，从而对应数组的下标
        //给s中的字母+1
        for(char c : s){
            Count[c-'a']++;
        }
        //给t中的字母-1
        for(char c : t){
            Count[c-'a']--;
        }
        //如何判断最后的出现个数相等，只有Count[]数组每个元素全为0
        for(int num : Count){
            if(num) return false;
        }
        return true;
    }
};

思考三-- 哈希表 – 双数组

在思考二中，只用了一个vector容器，但是用了两个for循环，一加一减

其实我可以只用两个vector容器，都进行++操作，或–操作，并且在一个for()循环中实现。

最后用一个if判断两个vector容器是否相等

思考三代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        //先把s，t的长度求出来
        int slength = s.length();
        int tlength = t.length();
        //如果s，t的长度不相等自然不可能是有效的字母异位词
        if (slength != tlength)   return false;
        //开辟两个包含26个元素的数组，计数s,t中出现的字母的个数，如果每个字母出现的个数相等，则s,t是有效的字母异位词
        vector<int> sCount(26,0);
        vector<int> tCount(26,0);
        //如何计数是一个问题，char是int，用s[i] - 'a'得到的是从0 - 25的数字，从而对应数组的下标
        for(int i = 0;i < slength;i++){
             //给t中的字母+1
            sCount[s[i] - 'a']++;
             //给t中的字母+1
            tCount[t[i] - 'a']++;
        }
        //如何判断最后的出现个数相等，只有sCount[]数组和tCount[]数组相等
        if(sCount==tCount)
            return true;
        return false;
    }
};

首先sCount==tCount编译器会用一个for()循环来判断，这产生了O(n)的时间复杂度

然后计数循环产生了O(n)的时间复杂度

总的来说这个算法时间复杂度为O(n)，但是应该比代码二要略微快一点

补充：代码三的剪枝是必要的，因为剩余的代码不具备处理长度不一样的字符串s，t的能力，而代码二可剪可不剪，影响的只是效率。

注：诸位站友如有所收获不如点个免费的赞，如有错误之处或有其它补充的点，请在评论区发表你的观点，看到必回。