【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]において，
a == c かつ b == d または a == d かつ b == c
カテゴリ：
- 問題難易度：Easy
- タグ：Array, Hash Table, Counting
- 使用技術：Counter（辞書）、tuple、組み合わせ計算（nC2）
解法①：全探索
TLE (Time Limit Exceeded)になります．
一番最初にシンプルに思いつく解法は全探索，今回の場合2重ループによる全要素の組み合わせです．
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つ以上存在する要素に対して，組み合わせの計算をする方法を試してみます．
ここでは下記の流れの処理を行っています．
- 元々の list dominoes から取り出した要素を sort し，tuple として再度 list に格納（sort しないと同じ要素として扱れないため，sort は必須）
- 新たに作成した list の中の各要素数をカウントする
- カウントした中で2以上の要素に対して，$_nC_2$ の組み合わせを答えに加算する（同一の要素から順不同・重複なしで 2 個を選ぶ）
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.が容易ですが，言語によっては面倒な時もあるかと思います．
その手順を行わずに実装する方法をご紹介します．
- dominoes から要素を1つずつ取り出し，[a, b] の組み合わせから key を作成
- その key が既に出現した回数を答えに加算
- その key の出現回数をインクリメント
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) | ソートされたペアの比較だけ 中間データなし |
| 解法② Counter + 組合せ | O(n) | O(n) | 中間リスト & カウント辞書あり |
| 解法③ ハッシュ + 出現回数 | O(n) | O(n) | ハッシュMap（Counter）使用 key数は高々45（1〜9の順列）だけど理論上 O(n) |
今後も時々，気になった LeetCode 問題を取り上げて解説していきます．
もし役に立ったら LGTM やコメントをいただけると励みになります！
おまけ
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;
};