Question

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 $cnt$ of length $100$ to record the number of occurrences of each two-digit number. For each domino, the two-digit number we concatenate is $x$, then the answer will increase by $cnt[x]$, and then we add $1$ to the value of $cnt[x]$. Continue to traverse the next domino, and we can count the number of all equivalent domino pairs.

The time complexity is $O(n)$, and the space complexity is $O(C)$. Here, $n$ is the number of dominoes, and $C$ is the maximum number of two-digit numbers concatenated in the dominoes, which is $100$.

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

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;
  }
};

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
}

Solution 2

class Solution:
  def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
    cnt = Counter()
    ans = 0
    for a, b in dominoes:
      x = a * 10 + b if a < b else b * 10 + a
      ans += cnt[x]
      cnt[x] += 1
    return ans