设计网站架构seo排名优化课程
本文将详细解析解决这个问题的思路，并逐步优化实现方案。
问题描述
给定两个字符串 word1 和 word2，如果通过以下操作可以将 word1 转换为 word2，则认为它们是接近的：
- 交换任意两个现有字符。
- 将一个现有字符的每次出现转换为另一个现有字符，并对另一个字符执行相同的操作。
你需要判断 word1 和 word2 是否接近。
示例
示例 1：
输入：word1 = "abc", word2 = "bca"
输出：true
解释：2 次操作从 word1 获得 word2 。
执行操作 1："abc" -> "acb"
执行操作 1："acb" -> "bca"
示例 2：
输入：word1 = "a", word2 = "aa"
输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。
示例 3：
输入：word1 = "cabbba", word2 = "abbccc"
输出：true
解释：3 次操作从 word1 获得 word2 。
执行操作 1："cabbba" -> "caabbb"
执行操作 2："caabbb" -> "baaccc"
执行操作 2："baaccc" -> "abbccc"
1657. 确定两个字符串是否接近 - 力扣（LeetCode）
解决思路
初步想法
最初的思路是通过使用 map 来记录字符及其出现的次数，然后通过 set 判断两个字符串的字符集是否一致，最后通过排序后的 vector 判断两个字符串的字符频次是否一致。
class Solution {
public:bool closeStrings(string word1, string word2) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);if(word1.size() != word2.size()) return false;// 首先判断map是不是都是一样的，包括char和int的个数；然后判断，是不是不管char，只要出现的次数一样就可以过unordered_map<char , int > m1 , m2;for(auto c : word1){m1[c] ++;}for(char d : word2){m2[d] ++;}if(m1 == m2) return true;unordered_set<char> s1(word1.begin() , word1.end());unordered_set<char> s2(word2.begin() , word2.end());if(s1 != s2) return false;vector<int> v1 , v2;for(auto pair : m1) v1.push_back(pair.second);for(auto pair : m2) v2.push_back(pair.second);sort(v1.begin() ,v1.end());sort(v2.begin() , v2.end());return v1 == v2;}
};
虽然初步思路可以解决问题，但在时间和空间复杂度上还有优化空间。
优化思路
1657. 确定两个字符串是否接近 - 力扣官方题解
官方解决方案利用了 word1 和 word2 仅包含小写字母这一条件，使用大小固定为 26 的 vector<int> 数组来记录字符频次。通过 ASCII 码减去 'a' 得到对应的下标，再进行操作。
class Solution {
public:bool closeStrings(string word1, string word2) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);vector<int> v1(26) , v2(26);for(auto c : word1){v1[c - 'a'] ++;}for(auto d : word2){v2[d - 'a'] ++;}for(int i = 0 ; i < 26 ; i ++){if(v1[i] == 0 && v2[i] > 0 || v1[i] > 0 && v2[i] == 0) return false;}sort(v1.begin() , v1.end());sort(v2.begin() , v2.end());return v1 == v2;}
};
详细解析
-
字符频次统计：
- 使用大小为 26 的
vector<int>数组count1和count2来记录word1和word2中每个字符的频次。通过c - 'a'得到对应的下标，这一步时间复杂度为O(n)。
- 使用大小为 26 的
-
字符集检查：
- 遍历
count1和count2，如果某个字符在一个字符串中出现而在另一个字符串中没有出现，则返回false。这一步的时间复杂度为O(1)，因为数组大小固定为 26。
- 遍历
-
字符频次数组排序和比较：
- 对
count1和count2进行排序，然后比较两个排序后的数组是否相等。排序的时间复杂度为O(26 log 26)，即O(1)。
- 对
为什么需要排序？
排序后的数组能直接比较每个字符的频次是否一致。这是因为交换字符不会改变频次，转换字符对频次排序也没有影响。通过排序并比较频次数组，我们能确保所有字符频次匹配。
复杂度分析
时间复杂度：
- 字符频次统计的时间复杂度为
O(n)，其中n为字符串的长度。 - 字符集检查的时间复杂度为
O(1)，因为count1和count2的大小固定为 26。 - 排序的时间复杂度为
O(26 log 26)，即O(1)。
总的时间复杂度为 O(n)。
空间复杂度：
- 使用了两个大小为 26 的
vector<int>数组，空间复杂度为O(1)。
总结
通过优化，我们利用字符串仅包含小写字母这一特性，将问题简化为固定大小的数组操作，实现了更高效的解决方案。这种方法充分利用了题目中的限制条件，极大地优化了时间和空间复杂度。