LeetCode #1128. Number of Equivalent Domino Pairs

# 【LeetCode #1128】Number of Equivalent Domino Pairs

## はじめに
とある企業で AI の実装・ソフトウェアの開発を行っています．
昨年から LeetCode を始め，easy レベルの問題から毎日少しずつ解いています．
最近やっと medium の問題に取り組み始めたので，これを機に時々 LeetCode の問題の解法について解説記事を書こうと思います．
メインは Python での実装です！
さて，第一回は easy レベルの問題についてです．

## 問題概要
与えられた二次元配列 **dominoes** に対して，下記の条件を満たす (i, j) の組み合わせをカウントする問題です．
* 0 <= i < j < dominoes.length
* dominoes[i] = [a, b]，dominoes[j] = [c, d]において， <br> a == c かつ b == d または a == d かつ b == c


**カテゴリ**：
- 問題難易度：Easy
- タグ：Array, Hash Table, Counting
- 使用技術：Counter（辞書）、tuple、組み合わせ計算（nC2）

## 解法①：全探索
**TLE (Time Limit Exceeded)になります．**
一番最初にシンプルに思いつく解法は全探索，今回の場合2重ループによる全要素の組み合わせです．
```python
class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        ans = 0
        for i in range(len(dominoes)):
            d1 = sorted(dominoes[i])
            for j in range(i+1, len(dominoes)):
                d2 = sorted(dominoes[j])
                ans += d1 == d2
        return ans
```
これは実装も簡単で分かりやすいですが，TLE になります．

## 解法②：要素の出現回数をカウント + 組み合わせ
次に少し考え方を変えてみて，同一の要素をカウントし，2つ以上存在する要素に対して，組み合わせの計算をする方法を試してみます．
ここでは下記の流れの処理を行っています．
1. 元々の list **dominoes** から取り出した要素を sort し，tuple として再度 list に格納（sort しないと同じ要素として扱れないため，sort は必須）
2. 新たに作成した list の中の各要素数をカウントする
2. カウントした中で2以上の要素に対して，$_nC_2$ の組み合わせを答えに加算する（同一の要素から順不同・重複なしで 2 個を選ぶ）
```python
class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        tmp = []
        for d in dominoes:
            tmp.append(tuple(sorted(d)))
        count = Counter(tmp)
        ans = 0
        for k, v in count.items():
            if v >= 2:
                ans += math.comb(v, 2)
        return ans
```
これは問題なく AC します．

## 解法③：tuple(sorted(d)) など使用しない解法
Python では解法②の1.が容易ですが，言語によっては面倒な時もあるかと思います．
その手順を行わずに実装する方法をご紹介します．
1. **dominoes** から要素を1つずつ取り出し，[a, b] の組み合わせから key を作成
1. その key が既に出現した回数を答えに加算
1. その key の出現回数をインクリメント
```python
class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        ans = 0
        count = Counter()
        BASE = 10
        for i in range(len(dominoes)):
            a, b = sorted(dominoes[i])
            key = a * BASE + b
            ans += count[key]
            count[key] += 1
        return ans
```
今回，a, b の制約は 1 <= a, b <= 9 のため，BASE = 10 としておけば，a * Base + b は同じ要素 a, b の時同一 key となり，異なる値の時は異なる key となります．
これを用いて **dominoes** 内の要素 [a, b] の出現回数を数え上げる手法です．

## まとめ
今回は初めての投稿ということで easy の問題を紹介しました．
速度とメモリとしては下記のような感じかと思います．
| 解法                | 時間計算量 | 空間計算量 | 解説                                              |
| ----------------- | ----- | ----- | ----------------------------------------------- |
| 解法① 全探索           | O(n²) | O(1)  | ソートされたペアの比較だけ<br>中間データなし                           |
| 解法② Counter + 組合せ | O(n)  | O(n)  | 中間リスト & カウント辞書あり                                |
| 解法③ ハッシュ + 出現回数   | O(n)  | O(n)  | ハッシュMap（Counter）使用<br>key数は高々45（1〜9の順列）だけど理論上 O(n) |

今後も時々，気になった LeetCode 問題を取り上げて解説していきます．  
もし役に立ったら LGTM やコメントをいただけると励みになります！

## おまけ
TypeScript だとこんな感じです．
```typescript
function numEquivDominoPairs(dominoes: number[][]): number {
    let ans: number = 0;
    let count = new Map<number, number>();
    for (const d of dominoes){
        let a: number = d[0];
        let b: number = d[1];
        const key:number = Math.min(a, b) * 10 + Math.max(a, b);
        if (count.has(key)){
            ans += count.get(key);
            count.set(key, count.get(key)! + 1);
        } else {
            count.set(key, 1)
        }
    }
    return ans;
};
```