Every day a Leetcode

题目来源：1657. 确定两个字符串是否接近

解法1：遍历

操作 1：交换任意两个现有字符。

操作 1 的本质：字符可以任意排列。统计 word1 和 word2 中的字符，如果字符及其出现次数都一样，只用操作 1 就可以从一个字符串得到另一个字符串，则认为两个字符串接近。

如果字符一样，但对应的出现次数不一样呢？这就需要用到操作 2 了。

操作 2：将一个现有字符的每次出现转换为另一个现有字符，并对另一个字符执行相同的操作。

操作 2 的本质：出现次数是可以交换的。

所以「出现次数」也像操作 1 那样，是可以任意排列的。

综上，如果 word1 和 word2 的字符一样，并且字符出现次数的集合是相同的，那么可以结合操作 1 和 2，把 word1 转化成 word2，即这两个字符串接近。

算法：

特判，如果 word1.size() != word2.size()，返回 false。计算两个字符串各自字符出现次数，cnt1 = alphaCount(word1), cnt2 = alphaCount(word2)。判断两个字符串的字符集合是否一样，如果不一样直接返回 false。如果两个字符串的字符集合一样，将它们排序，判断 cnt1 是否等于 cnt2，等于返回 true，不等于返回 false。

代码：

/*

* @lc app=leetcode.cn id=1657 lang=cpp

*

* [1657] 确定两个字符串是否接近

*/

// @lc code=start

class Solution

{

public:

bool closeStrings(string word1, string word2)

{

// 特判

if (word1.size() != word2.size())

return false;

vector cnt1 = alphaCount(word1), cnt2 = alphaCount(word2);

for (int i = 0; i < 26; i++)

if ((cnt1[i] == 0) != (cnt2[i] == 0))

return false;

sort(cnt1.begin(), cnt1.end());

sort(cnt2.begin(), cnt2.end());

// for (int i = 0; i < 26; i++)

// if (cnt1[i] != cnt2[i])

// return false;

// return true;

return cnt1 == cnt2;

}

// 辅函数

vector alphaCount(const string &s)

{

vector cnt(26, 0);

for (const char &c : s)

cnt[c - 'a']++;

return cnt;

}

};

// @lc code=end

结果：

复杂度分析：

时间复杂度：O(len1+len2+∣Σ∣log∣Σ∣)，其中 len1 和 len2 分别是字符串 word1 和 word2 的长度。遍历字符串需要 O(len1+len2) 的时间复杂度，对 cnt1 和 cnt2 排序的时间复杂度是 O(∣Σ∣log∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小。本题中字符均为小写英文字母，所以 ∣Σ∣ = 26。

空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小。本题中字符均为小写英文字母，所以 ∣Σ∣ = 26。

解法2：优化 - 位运算

判断字符集合是否一样，可以用位运算实现，也就是用二进制数（从低到高）第 i 位来存储是否有第 i 个小写英文字母，这样只需要判断两个二进制数是否一样即可。

代码：

/*

* @lc app=leetcode.cn id=1657 lang=cpp

*

* [1657] 确定两个字符串是否接近

*/

// @lc code=start

class Solution

{

public:

bool closeStrings(string word1, string word2)

{

// 特判

if (word1.size() != word2.size())

return false;

int mask1 = 0, mask2 = 0;

vector cnt1(26, 0), cnt2(26, 0);

for (const char &c : word1)

{

mask1 |= 1 << (c - 'a');

cnt1[c - 'a']++;

}

for (const char &c : word2)

{

mask2 |= 1 << (c - 'a');

cnt2[c - 'a']++;

}

sort(cnt1.begin(), cnt1.end());

sort(cnt2.begin(), cnt2.end());

return mask1 == mask2 && cnt1 == cnt2;

}

};

// @lc code=end

结果：

复杂度分析：

时间复杂度：O(len1+len2+∣Σ∣log∣Σ∣)，其中 len1 和 len2 分别是字符串 word1 和 word2 的长度。遍历字符串需要 O(len1+len2) 的时间复杂度，对 cnt1 和 cnt2 排序的时间复杂度是 O(∣Σ∣log∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小。本题中字符均为小写英文字母，所以 ∣Σ∣ = 26。

空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小。本题中字符均为小写英文字母，所以 ∣Σ∣ = 26。

精彩文章

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。