<p>Given a <strong>0-indexed</strong> <code>n x n</code> integer matrix <code>grid</code>, <em>return the number of pairs </em><code>(r<sub>i</sub>, c<sub>j</sub>)</code><em> such that row </em><code>r<sub>i</sub></code><em> and column </em><code>c<sub>j</sub></code><em> are equal</em>.</p>

<p>A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/06/01/ex1.jpg" style="width: 150px; height: 153px;" />
<pre>
<strong>Input:</strong> grid = [[3,2,1],[1,7,6],[2,7,7]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> There is 1 equal row and column pair:
- (Row 2, Column 1): [2,7,7]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/06/01/ex2.jpg" style="width: 200px; height: 209px;" />
<pre>
<strong>Input:</strong> grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are 3 equal row and column pairs:
- (Row 0, Column 0): [3,1,2,2]
- (Row 2, Column 2): [2,4,2,2]
- (Row 3, Column 2): [2,4,2,2]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 200</code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
    struct Trie {
        struct TrieNode {
            unordered_map<int, unique_ptr<TrieNode>> children;
            int counts = 0;
        };

        TrieNode root;

        void insert(const vector<int>& nums) {
            auto node = &root;
            for (auto num : nums) {
                if (node->children[num] == nullptr) {
                    node->children[num] = make_unique<TrieNode>();
                }
                node = node->children[num].get(); 
            }
            node->counts++;
        }

        int getCounts(const vector<int>& nums) {
            auto node = &root;
            for (auto num : nums) {
                if (node->children.find(num) == node->children.end()) {
                    return 0;
                }
                node = node->children[num].get(); 
            }
            return node->counts;
        }

        void getPaths(TrieNode* node, vector<int>& path, vector<pair<int, vector<int>>>& paths) {
            if (!node) {
                return;
            }

            if (node->counts) {
                paths.push_back({node->counts, path});
                return;
            }

            for (const auto& [num, child] : node->children) {
                path.push_back(num);
                getPaths(child.get(), path, paths);
                path.pop_back();
            }
        }

        vector<pair<int, vector<int>>> getPaths() {
            vector<int> path;
            vector<pair<int, vector<int>>> paths;
            getPaths(&root, path, paths);
            return paths;
        }



    };


public:
    int equalPairs(vector<vector<int>>& grid) {
        Trie row_trie;
        Trie col_trie;

        for (const auto& row : grid) {
            row_trie.insert(row);
        }

        for (int col = 0; col < grid.size(); col++) {
          vector<int> nums;
          for (int row = 0; row < grid.size(); row++) {
            nums.push_back(grid[row][col]);
          }
          col_trie.insert(nums);
        }

        int total = 0;
        for (auto [count, path] : row_trie.getPaths()) {
            total += count * col_trie.getCounts(path);
        }
        return total;
        
    }
};
143097