LeetCode Ts-2506. Count Pairs Of Similar Strings

    AllenLi
    CodingLeetCode Js-Hash Table

    You are given a 0-indexed string array words.
    Two strings are similar if they consist of the same characters.
    For example, “abca” and “cba” are similar since both consist of characters ‘a’, ‘b’, and ‘c’.
    However, “abacba” and “bcfd” are not similar since they do not consist of the same characters.
    Return the number of pairs (i, j) such that 0 <= i < j <= word.length - 1 and the two strings words[i] and words[j] are similar. 

    你給予一個 index 為 0 開始的字串陣列，叫做 words。
如果兩個字串由相同的字串集合組成，則代表他們相似。
舉例，「abca」和「cba」相似，因為他們都是由字串「a」、「b」、「c」所組成。
然而，「abacba」和「bcfd」不相似，因為他們不是由相同的字串組成。
回傳滿足 0 <= i < j <= word.length - 1 且 words[I] 和 words[j] 兩個字串相似的配對(i, j)數量。

    Example 1:

    Input: words = ["aba","aabb","abcd","bac","aabc"]
Output: 2
Explanation: There are 2 pairs that satisfy the conditions:
- i = 0 and j = 1 : both words[0] and words[1] only consist of characters 'a' and 'b'. 
- i = 3 and j = 4 : both words[3] and words[4] only consist of characters 'a', 'b', and 'c'.

    Example 2:

    Input: words = ["aabb","ab","ba"]
Output: 3
Explanation: There are 3 pairs that satisfy the conditions:
- i = 0 and j = 1 : both words[0] and words[1] only consist of characters 'a' and 'b'. 
- i = 0 and j = 2 : both words[0] and words[2] only consist of characters 'a' and 'b'.
- i = 1 and j = 2 : both words[1] and words[2] only consist of characters 'a' and 'b'.

    Example 3:

    Input: words = ["nba","cba","dba"]
Output: 0
Explanation: Since there does not exist any pair that satisfies the conditions, we return 0.

    Solution:
    首先，我們從題目給的例子中，我們需要整理 word 中的字串，
    我們發現 “abca”, “cba” 移除重複之後的 “a”, “b”, “c” = “abc” ，
    是相似的組合可以進行配對。
    而要達成這個判斷，我們會需要一個表，一個紀錄字串組合與次數的表。
    (ex. 這裡我用 HashMap (雜湊結構) 會比 HashTable (物件操作)的做法，在存取上更有效率。)
    接著我們就要計算 map 中每個字母組合出現的次數，這裡用簡單的組合公式(n * (n – 1)) / 2，來快速計算兩兩配對的數量。
    (ex. 組合公式 C(n,2) = n * (n − 1) / 2 ，從 n 個元素中任選 2 個，不分順序的組合數)

    Code 1: BigO(n)

    function similarPairs(words: string[]): number {
    const map: Map = new Map();
    let pairs: number = 0;
    for (const word of words) {
        const key: string = [...new Set(word)].sort().join("");
        map.set(key, (map.get(key) || 0) + 1);
    }    
    for (const count of map.values()) {
        pairs += (count * (count - 1)) / 2; 
    }
    return pairs;
};

    FlowChart:
    Example 1

    Input: words = ["aba","aabb","abcd","bac","aabc"]

map Map(3) { 'ab' => 2, 'abcd' => 1, 'abc' => 2 }

count 2, pairs 1
count 1, pairs 1
count 2, pairs 2
return pairs // 2

    Example 2

    Input: words = ["aabb","ab","ba"]

map Map(1) { 'ab' => 3 }

count 3, pairs 3
return pairs // 3

    Example 3

    Input: words = ["nba","cba","dba"]

map Map(3) { 'abn' => 1, 'abc' => 1, 'abd' => 1 }

count 1, pairs 0
count 1, pairs 0
count 1, pairs 0
return pairs // 0

    Related Posts