Welcome to Subscribe On Youtube
1128. Number of Equivalent Domino Pairs
Description
Given a list of dominoes
, dominoes[i] = [a, b]
is equivalent to dominoes[j] = [c, d]
if and only if either (a == c
and b == d
), or (a == d
and b == c
) - that is, one domino can be rotated to be equal to another domino.
Return the number of pairs (i, j)
for which 0 <= i < j < dominoes.length
, and dominoes[i]
is equivalent to dominoes[j]
.
Example 1:
Input: dominoes = [[1,2],[2,1],[3,4],[5,6]] Output: 1
Example 2:
Input: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]] Output: 3
Constraints:
1 <= dominoes.length <= 4 * 104
dominoes[i].length == 2
1 <= dominoes[i][j] <= 9
Solutions
Solution 1: Counting
We can concatenate the two numbers of each domino in order of size to form a two-digit number, so that equivalent dominoes can be concatenated into the same two-digit number. For example, both [1, 2]
and [2, 1]
are concatenated into the two-digit number 12
, and both [3, 4]
and [4, 3]
are concatenated into the two-digit number 34
.
Then we traverse all the dominoes, using an array
The time complexity is
-
class Solution { public int numEquivDominoPairs(int[][] dominoes) { int[] cnt = new int[100]; int ans = 0; for (var e : dominoes) { int x = e[0] < e[1] ? e[0] * 10 + e[1] : e[1] * 10 + e[0]; ans += cnt[x]++; } return ans; } }
-
class Solution { public: int numEquivDominoPairs(vector<vector<int>>& dominoes) { int cnt[100]{}; int ans = 0; for (auto& e : dominoes) { int x = e[0] < e[1] ? e[0] * 10 + e[1] : e[1] * 10 + e[0]; ans += cnt[x]++; } return ans; } };
-
class Solution: def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int: cnt = Counter() ans = 0 for a, b in dominoes: ans += cnt[(a, b)] cnt[(a, b)] += 1 if a != b: cnt[(b, a)] += 1 return ans
-
func numEquivDominoPairs(dominoes [][]int) (ans int) { cnt := [100]int{} for _, e := range dominoes { x := e[0]*10 + e[1] if e[0] > e[1] { x = e[1]*10 + e[0] } ans += cnt[x] cnt[x]++ } return }