📘 題目敘述
給定兩個字串 s1 和 s2，它們長度都為 n，並且只包含小寫英文字母。
你可以對任一個字串做任意次以下操作：
- 選兩個索引
i和j - 滿足
i < j - 且
j - i是偶數 - 然後交換這兩個位置的字元
請判斷是否可以透過這些操作，讓 s1 和 s2 變成相同字串。
如果可以，回傳 true；否則回傳 false。
條件限制
n == s1.length == s2.length1 <= n <= 10^5s1和s2只包含小寫英文字母
🧠 解題思路
我這題的想法是把字串拆成：
- 偶數位置那一組
- 奇數位置那一組
因為題目只允許交換距離為偶數的兩個位置，這代表被交換的兩個位置一定同奇偶。 也就是說：
- 偶數位置的字元只能和偶數位置互換
- 奇數位置的字元只能和奇數位置互換
所以一個字串經過任意次操作之後，本質上只能做到：
- 偶數位置那一組裡面的字元重新排列
- 奇數位置那一組裡面的字元重新排列
因此我只要分別比較：
s1和s2的偶數位置字元 multiset 是否相同s1和s2的奇數位置字元 multiset 是否相同
我這份寫法是直接把兩組字串拆出來後排序。 如果排序後都一樣，就代表可以透過交換把它們變成相同字串。
所有變數
es1：s1奇數位置的所有字元組成的字串es2：s2奇數位置的所有字元組成的字串os1：s1偶數位置的所有字元組成的字串os2：s2偶數位置的所有字元組成的字串
🪜 主要流程步驟
1. 先檢查兩個字串長度是否相同
我先判斷：
if (s1.size() != s2.size()) {
return false;
}
如果長度不同，那不可能透過題目允許的交換操作把它們變成同一個字串，所以直接回傳 false。
2. 把兩個字串分成奇數位置和偶數位置兩組
接著我準備四個字串：
string es1 = "", es2 = ""; // 奇數位置
string os1 = "", os2 = ""; // 偶數位置
然後掃過每個索引位置：
- 如果
i % 2 == 0，就把這個位置的字元放進偶數組 - 否則就放進奇數組
意思就是把 s1 和 s2 的字元各自拆成兩個部分。
這一步很重要，因為題目的操作不會改變字元所在位置的奇偶性。 所以最後能不能變一樣，關鍵就在於這兩組字元各自能不能配對起來。
3. 分別排序四個拆出來的字串
拆完之後，我就把這四個字串各自排序：
這樣做的目的，是把「能不能透過重排變成一樣」轉成「排序後是否相同」。
因為同一組內可以任意透過合法交換去調整順序， 所以真正要比的不是原本順序，而是：
- 這一組裡有哪些字元
- 每個字元各出現幾次
排序之後，如果兩個字串相同，就代表它們包含完全一樣的字元 multiset。
4. 最後同時比較偶數組和奇數組
最後我回傳：
return (os1 == os2 && es1 == es2) ? true : false;
也就是同時檢查：
- 偶數位置這一組排序後是否相同
- 奇數位置這一組排序後是否相同
只有兩組都相同，才代表：
- 偶數位置可以靠重排對上
- 奇數位置也可以靠重排對上
這樣整個字串才有可能透過合法操作變成一樣。
如果其中任一組不同，就代表至少有某些字元被困在錯誤的奇偶位置，無法透過操作修正，所以答案就是 false。
⏱️ 複雜度
設 n = s1.length。
- 時間複雜度：
O(n log n)我先掃一次字串做分組，之後對奇數組和偶數組排序，整體是O(n log n)。 - 空間複雜度：
O(n)我另外開了四個字串來存拆出來的奇數位置與偶數位置字元。
💻 程式碼實作
class Solution {
public:
bool checkStrings(string s1, string s2) {
if (s1.size() != s2.size()) {
return false;
}
string es1 = "", es2 = ""; // 奇數位置
string os1 = "", os2 = ""; // 偶數位置
for (int i = 0; i < s1.size(); i++) {
if (i % 2 == 0) {
os1 += s1[i];
os2 += s2[i];
} else {
es1 += s1[i];
es2 += s2[i];
}
}
sort(os1.begin(), os1.end());
sort(os2.begin(), os2.end());
sort(es1.begin(), es1.end());
sort(es2.begin(), es2.end());
return (os1 == os2 && es1 == es2) ? true : false;
}
};
🔗 題目連結
https://leetcode.com/problems/check-if-strings-can-be-made-equal-with-operations-ii/