三分钟理解字符串经典考题：有效的字母异位词

爱被打了一巴掌 2024-04-17 05:29 14阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

今天分享的题目来源于 LeetCode 上第 242 号问题，是一道字符串的经典考题。

### 题目描述 ###

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

**示例 1:**

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

**示例 2:**

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

**说明:**

你可以假设字符串只包含小写字母。

### 题目分析 ###

题目讲的是让你判断两个字符串中的字母是否一致，比如 **示例1** 中，`s` 包含字母 `a、n、g、r、m`，而 `t` 中也包含 `a、n、g、r、m` ，都是只有这五个字母，并且 **频次** 相同，只是顺序不同。

看到 **频次** 这个词，你脑海中第一想法是什么？

没错，就是 **哈希表** ！

解法思路很简单。

*  首先先判断两个字符串长度是否相同，不相同直接返回 `false`
 *  然后把 `s` 中所有的字符出现个数使用 **计数器** 统计起来，存入一个大小为 26 的数组中（注意题目的说明）
 *  最后再来统计 `t` 字符串，即遍历 `t` 时将对应的字母频次进行减少，如果期间 **计数器** 出现小于零的情况，则说明 `t` 中包含一个不存在于 `s` 中的字母，直接返回 `false`。
 *  最后检查计数器是否归零。

### 动画描述 ###

### 代码实现 ###

//@五分钟学算法
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] table = new int[26];
        for (int i = 0; i < s.length(); i++) {
            table[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            table[t.charAt(i) - 'a']--;
            //小技巧：如果在任何时候遍历后者时，计数器低于零，那肯定说明
            // t 中包含一个不存在于 s 中的字母 
            if (table[t.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }

--------------------

**本文相关阅读推荐：**

[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[一道腾讯面试题：厉害了我的杯][Link 2]

[十大经典排序算法动画与解析，看我就够了][Link 3]

[这或许是东半球分析十大排序算法最好的一篇文章][Link 4]

[面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

[看《长安十二时辰》可以了解哪些算法知识][Link 5]

GitHub 标星 3w+，很全面的算法和数据结构知识

![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/47d86db8adaa46b1a2a5b512453da83d.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485538&idx=1&sn=03adf88e7fe8bb7a6df9c1f77b2651b4&chksm=fa0e67e3cd79eef576563214c99121e5dbfc6332a95e45eade3735efc1472ba4c27be086b9bd&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 3]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485556&idx=1&sn=344738dd74b211e091f8f3477bdf91ee&chksm=fa0e67f5cd79eee3139d4667f3b94fa9618067efc45a797b69b41105a7f313654d0e86949607&scene=21#wechat_redirect
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485904&idx=1&sn=0eae783ce1b7c0383f41d76a269f511e&chksm=fa0e6651cd79ef47d31a0dba6909873974a964e81654cf702e3868da51fa9a695e7b9a383c1a&scene=21#wechat_redirect
[640_wx_fmt_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/ce01eaf380dd47668d6d51d26c26ac8e.png