# 2352. Equal Row and Column Pairs
###### tags: `Leetcode` `Medium` `Trie`
Link: https://leetcode.com/problems/equal-row-and-column-pairs/description/
## 思路
### Brute Force $O(n^3)$
检查每个col和row pair
### Trie $O(n)$
先把每个row都存进trie
然后看每个col能否在trie里找到完全相同的一个分支
## Code
### Brute Force $O(n^3)$

class Solution {
    public int equalPairs(int[][] grid) {
        int n = grid.length;
        int ans = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                //whether grid[i,:] is equal to grid[:,j]
                int k=0;
                for(k=0; k<n; k++){
                    if(grid[i][k]!=grid[k][j]) break;
                }
                if(k==n) ans++;
            }
        }
        return ans;
    }
}

### Trie $O(n)$

class Solution {
    class TrieNode {
        int count = 0;
        Map<Integer, TrieNode> map = new HashMap<>();
    }
    TrieNode root;
    int n;
    public int equalPairs(int[][] grid) {
        int ans = 0;
        n = grid.length;
        root = new TrieNode();
        for(int i=0; i<n; i++){
            insert(grid[i]);
        }
        for(int j=0; j<n; j++){
            ans += find(grid, j);
        }
        return ans;
    }
    public void insert(int[] row){
        TrieNode curr = root;
        for(int i=0; i<n; i++){
            if(!curr.map.containsKey(row[i])){
                curr.map.put(row[i], new TrieNode());
            }
            curr = curr.map.get(row[i]);
        }
        curr.count++;
    }
    public int find(int[][] grid, int j){
        TrieNode curr = root;
        for(int i=0; i<n; i++){
            if(!curr.map.containsKey(grid[i][j])) return 0;
            curr = curr.map.get(grid[i][j]);
        }
        return curr.count;
    }
}