本文將詳細(xì)解析解決這個(gè)問題的思路，并逐步優(yōu)化實(shí)現(xiàn)方案。

問題描述

給定兩個(gè)字符串 word1 和 word2，如果通過以下操作可以將 word1 轉(zhuǎn)換為 word2，則認(rèn)為它們是接近的：

1. 交換任意兩個(gè)現(xiàn)有字符。
2. 將一個(gè)現(xiàn)有字符的每次出現(xiàn)轉(zhuǎn)換為另一個(gè)現(xiàn)有字符，并對(duì)另一個(gè)字符執(zhí)行相同的操作。

你需要判斷 word1 和 word2 是否接近。

示例

示例 1：

輸入：word1 = "abc", word2 = "bca"
輸出：true
解釋：2 次操作從 word1 獲得 word2 。
執(zhí)行操作 1："abc" -> "acb"
執(zhí)行操作 1："acb" -> "bca"

示例 2：

輸入：word1 = "a", word2 = "aa"
輸出：false
解釋：不管執(zhí)行多少次操作，都無法從 word1 得到 word2 ，反之亦然。

示例 3：

輸入：word1 = "cabbba", word2 = "abbccc"
輸出：true
解釋：3 次操作從 word1 獲得 word2 。
執(zhí)行操作 1："cabbba" -> "caabbb"
執(zhí)行操作 2："caabbb" -> "baaccc"
執(zhí)行操作 2："baaccc" -> "abbccc"

1657. 確定兩個(gè)字符串是否接近 - 力扣（LeetCode）

解決思路

初步想法

最初的思路是通過使用 map 來記錄字符及其出現(xiàn)的次數(shù)，然后通過 set 判斷兩個(gè)字符串的字符集是否一致，最后通過排序后的 vector 判斷兩個(gè)字符串的字符頻次是否一致。

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的個(gè)數(shù)；然后判斷，是不是不管char，只要出現(xiàn)的次數(shù)一樣就可以過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;}
};

雖然初步思路可以解決問題，但在時(shí)間和空間復(fù)雜度上還有優(yōu)化空間。

優(yōu)化思路

1657. 確定兩個(gè)字符串是否接近 - 力扣官方題解

官方解決方案利用了 word1 和 word2 僅包含小寫字母這一條件，使用大小固定為 26 的 vector<int> 數(shù)組來記錄字符頻次。通過 ASCII 碼減去 'a' 得到對(duì)應(yīng)的下標(biāo)，再進(jìn)行操作。

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;}
};

詳細(xì)解析

1. 字符頻次統(tǒng)計(jì)：

   • 使用大小為 26 的 vector<int> 數(shù)組 count1 和 count2 來記錄 word1 和 word2 中每個(gè)字符的頻次。通過 c - 'a' 得到對(duì)應(yīng)的下標(biāo)，這一步時(shí)間復(fù)雜度為 O(n)。

2. 字符集檢查：

   • 遍歷 count1 和 count2，如果某個(gè)字符在一個(gè)字符串中出現(xiàn)而在另一個(gè)字符串中沒有出現(xiàn)，則返回 false。這一步的時(shí)間復(fù)雜度為 O(1)，因?yàn)閿?shù)組大小固定為 26。

3. 字符頻次數(shù)組排序和比較：

   • 對(duì) count1 和 count2 進(jìn)行排序，然后比較兩個(gè)排序后的數(shù)組是否相等。排序的時(shí)間復(fù)雜度為 O(26 log 26)，即 O(1)。

為什么需要排序？

排序后的數(shù)組能直接比較每個(gè)字符的頻次是否一致。這是因?yàn)榻粨Q字符不會(huì)改變頻次，轉(zhuǎn)換字符對(duì)頻次排序也沒有影響。通過排序并比較頻次數(shù)組，我們能確保所有字符頻次匹配。

復(fù)雜度分析

時(shí)間復(fù)雜度：

• 字符頻次統(tǒng)計(jì)的時(shí)間復(fù)雜度為 O(n)，其中 n 為字符串的長度。
• 字符集檢查的時(shí)間復(fù)雜度為 O(1)，因?yàn)?count1 和 count2 的大小固定為 26。
• 排序的時(shí)間復(fù)雜度為 O(26 log 26)，即 O(1)。

總的時(shí)間復(fù)雜度為 O(n)。

空間復(fù)雜度：

• 使用了兩個(gè)大小為 26 的 vector<int> 數(shù)組，空間復(fù)雜度為 O(1)。

總結(jié)

通過優(yōu)化，我們利用字符串僅包含小寫字母這一特性，將問題簡化為固定大小的數(shù)組操作，實(shí)現(xiàn)了更高效的解決方案。這種方法充分利用了題目中的限制條件，極大地優(yōu)化了時(shí)間和空間復(fù)雜度。