[Leetcode] 2352. Equal Row and Column Pairs (Medium)

概述

題目

https://leetcode.com/problems/equal-row-and-column-pairs/
給一 n*n grid，求 row & col 元素相同 (排序也需考慮) 的數量

心得

此題給的 constrain 有點小 (200)，故 BF 也可以過… O.o

Brute Force

思路

先取出 column element 再與 row 作比較

程式

class Solution(object):
    def equalPairs(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid)

        # 取出 column element
        arr = []
        for i in range(n):
            col = []
            for j in range(n):
                col.append(grid[j][i])
            arr.append(col)
        # print(arr)

        # 與 Row 做比較
        cnt = 0
        for i in range(n):
            for j in range(n):
                if arr[i] == grid[j]:
                    cnt += 1
        return cnt

Complexity

Time Complexity: O(n^3)
row, col 互比即 n^2，再加上每次要比 n 個元素，故 O(n^3)

Space Complexity: O(1)
基本上無使用到額外空間

Hash

思路

將 BF 方式以 Hash 優化

程式

class Solution(object):
    def equalPairs(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid)

        dic = Counter()
        arr = []
        for i in range(n):
            col = ""
            for j in range(n):
                col += str(grid[j][i])+"_"
            dic[col] += 1
            row = ""
            for j in range(n):
                row += str(grid[i][j])+"_"
            arr.append(row)
        # print(arr)

        cnt = 0
        for i in range(n):
            cnt += dic[arr[i]]
        return cnt