算法题 2024-04-01

来看下今天的算法题，这题是LeetCode的第242题：有效的字母异位词。

问题描述

来源：LeetCode第242题
难度：简单

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

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

示例1：

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

示例2：

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

  • 1 <= s.length, t.length <= 5 * 10^4

  • s 和 t 仅包含小写字母

问题分析

这题让判断两个字符串是否是字母异位词，所谓的字母异位词也就是两个字符串中每个字符出现的次数都是一样的，这道比较简单。

我们先统计第一个字符串中每个字符出现的次数，然后再统计第二个字符串中每个字符出现的次数（参照下面的python代码），统计第二个字符串的时候要减去对应字符的次数，如果为负，说明第二个字符串中某个字符比第一个字符串中相同的字符多，他们不可能是字母异位词，直接返回false。

声明长度为128的整型数组count，用于存储字符出现的频次。ASCII码表一共有128个字符。使用一个for循环（参照java，c++，c代码），如果最后count数组中每个元素都是0，说明两个字符串中每个字符的个数都是相等的，他们就是字母异位词，直接返回true。

1
2
3
4
5
6
7
8
9
10
11
public boolean isAnagram(String s, String t) {
  if (s.length() != t.length())
    return false;
  int[] count = new int[128];
  int c = 0;
  for (int i = 0; i < s.length(); i++) {
    if (++count[s.charAt(i)] == 1) c++;
    if (--count[t.charAt(i)] == 0) c--;
  }
  return c == 0;
}