前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >三分钟理解字符串经典考题:有效的字母异位词

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

作者头像
五分钟学算法
发布2019-08-23 17:14:34
4540
发布2019-08-23 17:14:34
举报

今天分享的题目来源于 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;
}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-08-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 五分钟学算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 题目分析
  • 动画描述
  • 代码实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档