2352. Equal Row and Column Pairs

LeetCode задача 2352

Задача

Дана квадратная матрица целых чисел grid размером n×n. Задача состоит в том, чтобы определить, сколько пар строк и столбцов в матрице идентичны по своему содержанию и порядку.

Строка и столбец считаются равными, если они содержат одни и те же элементы в том же порядке.

Подсказки

Для решения задачи можно воспользоваться тем фактом, что каждая строка и столбец представляют собой набор чисел. Если мы конвертируем их в строки, то можем сравнивать их друг с другом.

Подход

Вместо прямого сравнения каждой строки с каждым столбцом мы можем преобразовать каждую строку и столбец в кортеж(tuple) и использовать словарь(dict) для учета количества вхождений каждой уникальной строки. При проходе по столбцам мы можем напрямую обращаться к нашему словарю, чтобы узнать, совпадает ли представление кортежа столбца с любой строкой.

Почему кортежи?

Прежде чем углубляться в оптимизированный подход, важно понимать роль кортежей. Мы преобразуем строки и столбцы в кортежи, потому что:

• Кортежи неизменяемы: их содержимое не может быть изменено после создания.
• Они могут использоваться в качестве ключей в словарях, в отличие от списков или множеств. Это свойство критически важно для нашего решения.
• Кортежи сохраняют порядок элементов, что важно для требований нашей задачи.

Алгоритм

1. Преобразуем каждую строку в кортеж и подсчитаем ее вхождения с помощью словаря.
2. Пройдем каждый столбец, преобразуем его в кортеж.
3. Проверим, существует ли кортеж столбца в нашем словаре.
   1. Если да, увеличиваем счетчик на количество вхождений этого кортежа.

Решение

def equalPairs(self, grid: List[List[int]]) -> int:
    count = 0
    rows = {}

    # Храним кортежи строк и их количество вхождений
    for row in grid:
        row = tuple(row)
        rows[row]= 1 + rows.get(row, 0)
    
    # Для каждого столбца проверяем, существует ли кортеж столбца в словаре строк
    n = len(grid)
    for c in range(n):
        col = tuple(grid[r][c] for r in range(n))
        count += rows.get(col, 0)
        
    return count