建设一个门户网站需要多久,山西省工程招标网,做羞羞的网站,网站的标签修改242. 有效的字母异位词
难度#xff1a;easy\color{Green}{easy}easy 题目描述
给定两个字符串 sss 和 ttt #xff0c;编写一个函数来判断 ttt 是否是 sss 的字母异位词。
注意#xff1a; 若 sss 和 ttt 中每个字符出现的次数都相同#xff0c;则称 sss 和 ttt 互为字…242. 有效的字母异位词
难度easy\color{Green}{easy}easy 题目描述
给定两个字符串 sss 和 ttt 编写一个函数来判断 ttt 是否是 sss 的字母异位词。
注意 若 sss 和 ttt 中每个字符出现的次数都相同则称 sss 和 ttt 互为字母异位词。
示例 1:
输入: s anagram, t nagaram
输出: true示例 2:
输入: s rat, t car
输出: false提示:
1s.length,t.length5∗1041 s.length, t.length 5 * 10^{4}1s.length,t.length5∗104sss 和 ttt 仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办你能否调整你的解法来应对这种情况
本题和 LeetCode 383. 赎金信 类似。 算法
(字符统计)
ttt 是 sss 的异位词等价于「两个字符串中字符出现的种类和次数均相等」。由于字符串只包含 26 个小写字母因此我们可以维护一个长度为 26 的频次数组 cnt先遍历记录字符串 sss 中字符出现的频次然后遍历字符串 ttt减去 cnt 中对应的频次如果出现 cnt[i] 0则说明 ttt 包含一个不在 sss 中的额外字符返回 false 即可。
复杂度分析 时间复杂度O(n)O(n)O(n)其中 nnn 是字符串的长度。需要遍历字符串两次 空间复杂度 : O(1)O(1)O(1)仅需要常量的空间来存储。
C 代码
class Solution {
public:bool isAnagram(string s, string t) {if (s.size() ! t.size()) return false;vectorint cnt(26, 0);for (auto c : s) {cnt[c - a] ;}for (auto c : t) {cnt[c - a] --;if (cnt[c - a] 0) return false;}return true;}
};进阶C 代码
Unicode 是为了解决传统字符编码的局限性而产生的方案它为每个语言中的字符规定了一个唯一的二进制编码。而 Unicode 中可能存在一个字符对应多个字节的问题为了让计算机知道多少字节表示一个字符面向传输的编码方式的 UTF−8 和 UTF−16 也随之诞生逐渐广泛使用。
进阶问题的核心点在于「字符是离散未知的」因此我们用哈希表维护对应字符的频次即可。
class Solution {
public:bool isAnagram(string s, string t) {unordered_mapchar, int a, b;for (auto c: s) a[c] ;for (auto c: t) b[c] ;return a b;}
};
