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

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

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

今天分享的题目来源于 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;
}



本文相关阅读推荐:


毕业十年后,我忍不住出了一份程序员的高考试卷

一道腾讯面试题:厉害了我的杯

十大经典排序算法动画与解析,看我就够了!(配代码完全版)

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

面试官,我会写二分查找法!对,没有 bug 的那种!

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

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

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