LeetCode 242. 有效的字母异位词

---

LeetCode 242. 有效的字母异位词

1、题目

力扣题目链接：242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意： 若 s 和 _t _中每个字符出现的次数都相同，则称 s 和 _t _互为字母异位词。

示例 1:

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

示例 2:

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

提示:

• 1 <= s.length, t.length <= 5 * 104
• s 和 t 仅包含小写字母

进阶： 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

2、排序

代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        // 检查两个字符串的长度是否相等，如果不相等，直接返回false，因为长度不同的字符串无法成为字母异位词
        if (s.size() != t.size()) {
            return false;
        }
 
        // 对字符串s和t进行排序，使得其中的字符按照字母顺序排列 
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
 
        // 比较排序后的两个字符串是否相等，如果相等，说明它们包含的字符种类和数量完全一样，只是字符的顺序不同，因此是字母异位词
        return s == t;
    }
};

复杂度分析

时间复杂度：O(nlog⁡n)，其中 n 为 s 的长度。排序的时间复杂度为 O(nlog⁡n)，比较两个字符串是否相等时间复杂度为 O(n)，因此总体时间复杂度为 O(nlog⁡n+n)=O(nlog⁡n)。

空间复杂度：O(log⁡n)。排序需要 O(log⁡n) 的空间复杂度。

3、哈希表

代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        // 检查两个字符串的长度是否相等，如果不相等，直接返回false，因为长度不同的字符串无法成为字母异位词
        if (s.size() != t.size()) {
            return false;
        }

        // 用于记录每个字母出现的次数
        int record[26] = {0};

        // 遍历字符串，每出现一次，对应位置的值加1
        for (int i = 0; i < s.size(); ++i) {
            record[s[i] - 'a']++;
        }

        // 遍历字符串，每出现一次，对应位置的值减1
        // 如果在减1的过程中，对应位置的值小于0，说明字符串s和t不是字母异位词，直接返回false
        for (int i = 0; i < t.size(); ++i) {
            record[t[i] - 'a']--;

            if (record[t[i] - 'a'] < 0) {
                return false;
            }
        }

        // 如果以上所有字符都成功完成了计数和减1操作，没有产生负值，说明字符串s和t是字母异位词，返回true  
        return true;
    }
};

复杂度分析

时间复杂度：O(n)，其中 n 为 s 的长度。
空间复杂度：O(S)，其中 S 为字符集大小，此处 S=26。

原文地址：https://blog.csdn.net/2301_80211119/article/details/137755455

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！