1657. Determine if Two Strings Are Close (使用 C 語言解題)

1657. Determine if Two Strings Are Close

Solved

Medium

Topics

Companies

Hint

Two strings are considered close if you can attain one from the other using the following operations:

• Operation 1: Swap any two existing characters.
  • For example, abcde -> aecdb
• Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
  • For example, aacabb -> bbcbaa (all a's turn into b's, and all b's turn into a's)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

 

Example 1:

Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"

Example 2:

Input: word1 = "a", word2 = "aa"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3:

Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Explanation: You can attain word2 from word1 in 3 operations.
Apply Operation 1: "cabbba" -> "caabbb"
Apply Operation 2: "caabbb" -> "baaccc"
Apply Operation 2: "baaccc" -> "abbccc"

 

Constraints:

• 1 <= word1.length, word2.length <= 105
• word1 and word2 contain only lowercase English letters.

google 翻譯：

如果可以使用以下操作從另一個字串獲得一個字串，則認為兩個字串是接近的：

操作1：交換任兩個現有字元。
例如，abcde -> aecdb
        操作2：將每個出現的一個現有字符轉換為另一個現有字符，並對另一個字符執行相同操作。
例如，aacabb -> bbcbaa（所有a都變成b，所有b都變成a）
您可以根據需要多次對任一字串使用這些操作。

給定兩個字串，word1 和 word2，如果 word1 和 word2 接近，則傳回 true，否則傳回 false。

想法一：

分兩 hash 陣列，
第一個 hash 存放字串1的字元個數
第二個 hash 存放字串2的字元個數
兩字串的字元在兩邊都要同時有出現過
字元出現的個數要完全相同

寫法一：

// 排序用
int cmp(int *a, int *b) {
    return *a > *b;
}
bool closeStrings(char* word1, char* word2) {
    int *hash1 = calloc(27, sizeof(int)); // 存放字串1的字元個數
    int *hash2 = calloc(27, sizeof(int)); // 存放字串2的字元個數
    int size = 0;
    char *p;

    // 字串長度不相等直接回傳 false
    if(strlen(word1) != strlen(word2))
        return false;

    // 計算字串1的字元個數
    p = word1;
    for(; *p; p++) {
        hash1[*p - 'a']++;
    }

    // 計算字串2的字元個數
    p = word2;
    for(; *p; p++) {
        hash2[*p - 'a']++;
    }

    // 查看 hash
    for(int i=0; i<27; i++) {
        // 這個字元兩邊都要出現，或是都沒出現，才繼續判斷
        if((hash1[i] && !hash2[i]) || (!hash1[i] && hash2[i]))
            return false;
        else if(hash1[i]) { // 這個字元都有出現
            hash1[size] = hash1[i]; // 保留字元都有出現的個數
            hash2[size] = hash2[i]; // 保留字元都有出現的個數
            size++;
        }
    }
    // 排序
    qsort(hash1, size, sizeof(int), cmp);
    qsort(hash2, size, sizeof(int), cmp);
    // 排序後數值要一模一樣才可回傳 true
    for(int i=0; i<size; i++) {
        if(hash1[i] != hash2[i])
            return false;
    }
    return true;
}

結果一：

結果還行...也沒什麼想改的了...