242. 有效的字母异位词

一、题述

给定两个字符串 st ,编写一个函数来判断 t 是否是 s 的字母异位词。

注意:若 st中每个字符出现的次数都相同,则称 s t 互为字母异位词。

示例 1:

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

示例 2:

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

提示:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?

二、题解

1、排序

我们可以通过排序后两字符串是否相等为条件判断排序后的st是否相等,从而判断两者是否互为字母异位词。

class Solution {
public:
    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;
    }
};

2、哈希表

首先判断两数组长度是否相等,其次,建立一个record数组,对s数组进行遍历,只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可,并不需要记住字符a的ASCII.

同样的,在遍历t数组的时候只需对record进行-1操作即可。

最后检查,若record数组如果有的元素不为零0,说明字符串s和t一定是谁多了字符或者谁少了字符,return false;反之则s & t 互为字母异位词。

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        vector<int> record(26, 0);
        for (auto& ch: s) {
            record[ch - 'a']++;
        }
        for (auto& ch: t) {
            record[ch - 'a']--;
            if (record[ch - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

复杂度分析

  • 时间复杂度:遍历,O(N)。
  • 空间复杂度:只定义了一个常量大小的辅助数组,所以复杂度仅为O(1)。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇