1657. Determine if Two Strings Are Close

📘 題目敘述

給定兩個字串 word1 與 word2，若你可以對其中任一字串執行以下操作任意次，並使兩字串變得相同，則回傳 true，否則回傳 false：

操作 1：交換任意兩個已存在的字元位置（等價於任意重新排列字元）。
操作 2：選兩個已存在的字元 x 與 y，把字串中所有 x 都改成 y，同時把所有 y 都改成 x（等價於「交換兩種字元的身分」）。

條件限制

1 ≤ word1.length, word2.length ≤ 10^5
word1、word2 只包含小寫英文字母

🧠 解題思路

我的想法是把「能不能變成一樣」拆成兩個互不干擾的條件來檢查：

字母種類要一樣 因為操作 2 只能在「已存在的字母」之間互換，所以如果 word1 出現過某個字母、word2 完全沒出現，那無論怎麼換都不可能補出來（反之亦然）。 → 所以我先比較兩邊的「出現過哪些字母」是否一致。
出現次數的分布要一樣（當作多重集合） 操作 1 只會改位置，不改次數；操作 2 會把兩個字母的「次數」互換。所以重點是：兩邊的每種字母次數，排序後要能一一對上。 → 我把每個字母的出現次數收集起來，排序後比較是否完全相同。

因此我用了四個 vector：

兩個用來存「字母種類」
兩個用來存「各字母的出現次數（並排序後比較）」

最後兩個條件都通過才回傳 true。

所有變數

occ1：word1 每個字母的出現次數集合（之後會排序）
occ2：word2 每個字母的出現次數集合（之後會排序）
now1：word1 出現過的字母種類（排序後逐一收集）
now2：word2 出現過的字母種類（排序後逐一收集）
now：掃描排序後字串時，用來記錄「目前正在計數的字母」
count：目前這個字母累積出現了幾次

🪜 主要流程步驟

1. 先做長度檢查

如果 word1.size() != word2.size()，那不可能變成一樣，直接回傳 false。

2. 排序兩個字串，方便統計每個字母的連續段

我先 sort(word1)、sort(word2)
這樣同一個字母會被排在一起，就能用「掃一遍」的方式統計每個字母的出現次數。

3. 掃描 `word1`：建立 `now1`（字母種類）與 `occ1`（次數集合）

我從左到右掃描排序後的 word1：

遇到新字母（now != i）
- 代表上一段字母結束了，把上一段的 count 收進 occ1
- 把新字母收進 now1
- 把 count 重設為 1（開始數新字母）
遇到同字母（now == i）
- count++ 繼續累積

掃描結束後，再把最後那一段的 count 補進去。

4. 同樣方式掃描 `word2`：建立 `now2` 與 `occ2`

流程與上一步完全相同，只是目標換成 word2。

5. 比較條件 A：字母種類是否一致

如果 now1 與 now2 內容不同 → 回傳 false （表示兩邊存在的字母集合不同，操作 2 也救不了）

6. 比較條件 B：次數集合是否一致

我把 occ1、occ2 各自排序後比較
若排序後仍有任一位置不同 → 回傳 false （表示次數分布無法靠「交換字母身分」對齊）

7. 兩個條件都通過 → 回傳 `true`

💻 程式碼實作

class Solution {
public:
    bool closeStrings(string word1, string word2) {
        if (word1.size() != word2.size()) {
            return false;
        }
        vector<int> occ1;
        vector<int> occ2;
        vector<char> now1;
        vector<char> now2;
        char now = ' ';
        int count = 0;
        sort(word1.begin(), word1.end());
        sort(word2.begin(), word2.end());
        for (char i : word1) {
            if (now != i) {
                occ1.push_back(count);
                now1.push_back(i);
                count = 1;
                now = i;
            } else {
                count++;
            }
        }
        if (count) {
            occ1.push_back(count);
            now1.push_back(now);
        }
        sort(occ1.begin(), occ1.end());

        now = ' ';
        count = 0;
        for (char j : word2) {
            if (now != j) {
                occ2.push_back(count);
                now2.push_back(j);
                count = 1;
                now = j;
            } else {
                count++;
            }
        }
        if (count) {
            occ2.push_back(count);
            now2.push_back(now);
        }
        sort(occ2.begin(), occ2.end());

        if (occ1.size() != occ2.size()) {
            return false;
        }
        for (int k = 0; k < occ1.size(); k++) {
            if (occ1[k] != occ2[k] || now1[k] != now2[k]) {
                return false;
            }
        }
        return true;
    }
};

🔗 題目連結

https://leetcode.com/problems/determine-if-two-strings-are-close/