如果两个字符串word1
和word2
中从'a'
到'z'
每一个字母出现的频率之差都不超过3
,那么我们称这两个字符串word1
和word2
几乎相等。
给你两个长度为n
的字符串word1
和word2
,如果word1
和word2
几乎相等,请你返回true
,否则返回false
。
注意:
一个字母x
的出现频率指的是它在字符串中出现的次数。
word1和word2的长度相同。
word1和word2都只包含小写英文字母。
示例:
输入:word1 = “aaaa”, word2 = “bccb”
输出:false
思路:
该题目就是给定两个字符串,让我们判断这两个字符串中对应字母的出现次数之差是否大于3,主要考察两点:
- 遍历字符串。
- 哈希表的使用。
解题步骤如下:
- 创建哈希表,开辟26个位置以供使用。
- 遍历word1,将每个字母出现的次数统计到哈希表中。
- 遍历word2,与哈希表中统计的字母进行抵消。
- 遍历哈希表,判断是否有差值大于3的字母,若有则返回false,否则返回true。
代码如下:
class Solution {
public:
bool checkAlmostEquivalent(string word1, string word2) {
//1、创建哈希表,提前开辟26个位置并初始化为0
vector<int> table(26, 0);
//2、遍历word1,将每个字母出现的次数统计到哈希表中
for (auto e : word1)
{
table[e - 'a']++;
}
//3、遍历word2,与哈希表中统计的字母进行抵消
for (auto e : word2)
{
table[e - 'a']--;
}
//4、遍历哈希表,判断是否有差值大于3的字母
for (auto e : table)
{
if (abs(e) > 3)
return false;
}
return true;
}
};