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(nlogn),其中 n 为 s 的长度。排序的时间复杂度为 O(nlogn),比较两个字符串是否相等时间复杂度为 O(n),因此总体时间复杂度为 O(nlogn+n)=O(nlogn)。
空间复杂度:O(logn)。排序需要 O(logn) 的空间复杂度。
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)!