Leetcode 1657 - Determine if Two Strings Are Close

題目

Problem#

給你兩個字串 word1, word2 你可以對它做以下兩個操作:

1. 交換任意兩個字元 e.g. abcde -> aecdb
2. 選擇一組字元(不限長度、可以不用連續)，可以互相交換字元 e.g. aacabb -> bbcbaa

你可以做無限次操作，把 word1 和 word2 做完操作後會一樣回傳 true 反之回傳 false。

測資限制#

• $1 \le n \le 10^5$

想法#

第一種操作可以讓字元到任意位置，第二種操作可以讓該字元頻率交換
所以判斷兩個字串一不一樣就變成了判斷兩個字串字元出現種類，和字元出現次數(不看種類)
按此規則判斷即可

AC Code#

Copy

class Solution {
public:
    bool closeStrings(string word1, string word2)
    {
        int a[26]={}, b[26]={};
        for(char c : word1) a[c-'a']++;
        for(char c : word2) b[c-'a']++;
 
        vector<bool> ea(26, 0), eb(26, 0); // if char exists = ea[ch]
        vector<int> va, vb; // count of same char
        for(int i = 0; i < 26; i++)
        {
            if(a[i])
            {
                ea[i] = 1;
                va.push_back(a[i]);
            }
            if(b[i])
            {
                eb[i] = 1;
                vb.push_back(b[i]);
            }
        }
 
        sort(va.begin(), va.end());
        sort(vb.begin(), vb.end());
        return va == vb && ea == eb;
    }
};

view raw leetcode/1657.cpp delivered with ❤ by emgithub

• 時間複雜度: $\mathcal{O}(n\log{n})$
• 空間複雜度: $\mathcal{O}(n)$