外贸展示型模板网站,手机推广软文,有名的公关公司,整站seo优化推广本文将详细解析解决这个问题的思路#xff0c;并逐步优化实现方案。
问题描述
给定两个字符串 word1 和 word2#xff0c;如果通过以下操作可以将 word1 转换为 word2#xff0c;则认为它们是接近的#xff1a;
交换任意两个现有字符。将一个现有字符的每次出现转换为另…本文将详细解析解决这个问题的思路并逐步优化实现方案。
问题描述
给定两个字符串 word1 和 word2如果通过以下操作可以将 word1 转换为 word2则认为它们是接近的
交换任意两个现有字符。将一个现有字符的每次出现转换为另一个现有字符并对另一个字符执行相同的操作。
你需要判断 word1 和 word2 是否接近。
示例
示例 1
输入word1 abc, word2 bca
输出true
解释2 次操作从 word1 获得 word2 。
执行操作 1abc - acb
执行操作 1acb - bca示例 2
输入word1 a, word2 aa
输出false
解释不管执行多少次操作都无法从 word1 得到 word2 反之亦然。示例 3
输入word1 cabbba, word2 abbccc
输出true
解释3 次操作从 word1 获得 word2 。
执行操作 1cabbba - caabbb
执行操作 2caabbb - baaccc
执行操作 2baaccc - abbccc1657. 确定两个字符串是否接近 - 力扣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_mapchar , int m1 , m2;for(auto c : word1){m1[c] ;}for(char d : word2){m2[d] ;}if(m1 m2) return true;unordered_setchar s1(word1.begin() , word1.end());unordered_setchar s2(word2.begin() , word2.end());if(s1 ! s2) return false;vectorint 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 的 vectorint 数组来记录字符频次。通过 ASCII 码减去 a 得到对应的下标再进行操作。
class Solution {
public:bool closeStrings(string word1, string word2) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);vectorint 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 的 vectorint 数组 count1 和 count2 来记录 word1 和 word2 中每个字符的频次。通过 c - a 得到对应的下标这一步时间复杂度为 O(n)。 字符集检查 遍历 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 的 vectorint 数组空间复杂度为 O(1)。
总结 通过优化我们利用字符串仅包含小写字母这一特性将问题简化为固定大小的数组操作实现了更高效的解决方案。这种方法充分利用了题目中的限制条件极大地优化了时间和空间复杂度。
