跳转至

242 有效的字母异位词

leetcode

Solution

暴力解法(超时)

class Solution {
public:
    bool judge(string s, string t) {
        // 默认s.size() > t.size()
        vector<bool> isVisited(t.size(), false);
        for (int i = 0; i < s.size(); i++) {
            bool find = false;
            for (int j = 0; j < t.size(); j++) {
                if (!isVisited[j] && s[i] == t[j]) {
                    isVisited[j] = true;
                    find = true;
                    break;
                }
            }
            if (!find)
                return false;
        }
        return true;
    }
    bool isAnagram(string s, string t) {
        if (s.size() > t.size())
            return judge(s, t);
        else
            return judge(t, s);
    }
};

复杂度分析

  • 时间复杂度:\(O(n^2)\)
  • 空间复杂度:\(O(n)\)

哈希表

题目说了“s 和 t 仅包含小写字母”,因此哈希表key只有26个,并且是连续的,数组就可以满足。

计数思想:s出现的字符加1,t出现的字符减1,如果最后计数器不为0,则说明s字符和t字符不匹配

class Solution {
public:
    bool isAnagram(string s, string t) {
        int hashMap[26] = {0};
        for(char c : s){
            hashMap[c - 'a']++;
        }
        for(char c : t){
            hashMap[c - 'a']--;
        }
        for(int i : hashMap){
            if(i != 0)
                return false;
        }
        return true;
    }
};

复杂度分析:

  • 时间复杂度: \(O(n)\)
  • 空间复杂度: \(O(n)\)