当前位置：首页 > article >正文

算法—有效的字母异位词

article 2024/12/22 14:32:06

一道 LeetCode 简单题，题目链接：https://leetcode.cn/problems/valid-anagram/description/

题目

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

示例1：

输入: s = “anagram”, t = “nagaram”

输出: true

示例2：

输入: s = “rat”, t = “car”

输出: false

思路

先来分析一下题目：”字母异位“意思就是两个字符串中的某些字符只是位置不同，但是个数和种类都是一样的。

我的思路：

分为两个条件判断：

判断字符个数是不是一样的，不一样就不是异位词
判断字符种类是不是一样的，如果都包含同样的字符，只是顺序不同，直接返回。

代码实现：

首先判断两个字符长度，不一样，返回 false
用查询表的思路，因为都是小写字母，所以只需要定义一个长度 26 的整数数组
先遍历字符串 s，每个字符减去小写字母 a，就是这个字符在数组中的索引位置，只要有这个字符，对应的索引就自增 1
再遍历字符串 t，字符对应的索引位置自减 1
最后，判断这个整数数组中，有没有不是 0 的数，如果有，就返回 false
遍历结束，返回 true

代码

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] arr = new char[26];
        for (char c : s.toCharArray()) {
            arr[c - 'a']++;
        }
        for (char c : t.toCharArray()) {
            arr[c - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (arr[i] != 0) {
                return false;
            }
        }
        return true;
    }
}