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

Leetcode_242.有效的字母异位词

news 2025/7/30 17:01:11

在这里插入图片描述
拿到题我们先来分析一下，对于这道题目，题中给定了两个字符串，通过一系列的判断，来得出这个字符串是否为字母异位词。字母异位词，通过示例得到，就是两个字符串中的字母出现的次数相同，只是顺序形同或者不同。统计出现的个数我们想到了哈希表，这道题由于是关联了字母和出现的次数，所以首选map类型的容器，由于map底层是红黑树实现，查找效率过于慢，这里我们使用unordered_map，底层是哈希实现，查找速度更优。

下来解释一下代码的逻辑思路：

字母异位相同首先要求两个字符串的长度要一致，所以第一步，判断字符串的长度是否相同，如果不相同直接返回false
首先将字符串 s 存入容器中,字符串中出现一次这个字符，那么这个字符所对应的value值就加一，在c++ unordered_map容器中，如果字符不存在，会自动初始化为0然后+1
下来遍历 t 字符串，如果 mp 容器中已经出现了当前的字符，那么这个字符所对应的value值减1
最后得到，如果容器中的所有字符所对应的value值都为0，则这两个字符串为字母异位词

c++代码：

class Solution {
public:bool isAnagram(string s, string t) {// 如果两个字符串长度不同，直接返回false（因为字母异位词必须长度相同）if(s.size() != t.size()) return false;// 使用哈希表统计每个字符的出现次数unordered_map<char, int> mp;int len = s.size();// 遍历字符串s，统计每个字符出现的次数for(int i = 0; i < len; i++){mp[s[i]]++; // 如果字符不存在，会自动初始化为0然后+1}// 遍历字符串t，减少哈希表中对应字符的计数for(int i = 0; i < t.size(); i++){// 如果当前字符存在于哈希表中，减少其计数if(mp.find(t[i]) != mp.end()){mp[t[i]]--;}// 如果字符不存在，可以提前返回false（后面统一检查）}// 检查哈希表中所有字符的计数是否归零for(auto &e : mp){// 如果有字符的计数不为0，说明不是字母异位词if(e.second != 0) return false;}// 所有字符计数都为0，是字母异位词return true;}
};

Java代码：

class Solution {public boolean isAnagram(String s, String t) {if (s.length() != t.length()) {return false;}HashMap<Character, Integer> mp = new HashMap<>();// 统计 s 的字符频率for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);mp.put(c, mp.getOrDefault(c, 0) + 1);}// 用 t 的字符减少计数for (int i = 0; i < t.length(); i++) {char c = t.charAt(i);if (!mp.containsKey(c)) {return false; // t 包含 s 没有的字符}mp.put(c, mp.get(c) - 1);if (mp.get(c) < 0) {return false; // t 的某个字符比 s 多}}// 检查所有计数是否为 0for (int count : mp.values()) {if (count != 0) {return false;}}return true;}
}

但是这种方法的效率比较低，由于这道题只有小写字母，小写字母只有26个，因此我们可以使用数组来模拟哈希表，进一步的提升效率

c++代码：

class Solution {
public:bool isAnagram(string s, string t) {if(s.size()!=t.size()) return false;int hash[26];int len=s.size();memset(hash,0,sizeof(hash));for(int i=0;i<len;i++){hash[s[i]-97]++;}for(int i=0;i<len;i++){hash[t[i]-97]--;}for(int i=0;i<26;i++){if(hash[i]!=0) return false;}return true;}
};