Leetcode-6125: equal row and column pairs

subject

Topic linking

I'll give you a subscript from 0 Start 、 The size is n x n The integer matrix of grid , Return to satisfaction Ri Row sum Cj Row and column pairs with equal columns (Ri, Cj) Number of .

If rows and columns contain the same elements in the same order （ Equal array ）, They are equal .

Example 1：

 Input ：grid = [[3,2,1],[1,7,6],[2,7,7]]
 Output ：1
 explain ： There is a pair of equal row and column pairs ：
- ( The first  2  That's ok , The first  1  Column )：[2,7,7]

Example 2：

 Input ：grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
 Output ：3
 explain ： There are three pairs of equal row and column pairs ：
- ( The first  0  That's ok , The first  0  Column )：[3,1,2,2]
- ( The first  2  That's ok ,  The first  2  Column )：[2,4,2,2]
- ( The first  3  That's ok ,  The first  2  Column )：[2,4,2,2]

Problem solving

Method 1 ： Code as string+ Hash

Set the horizontal direction , Code as string
Set the vertical direction , Programming string,
For example, for ：
{
{1,11},
{11,1}
}
horizontal direction , Can be coded as "#1#11" and "#11#1"
In the vertical direction , Can be coded as "#1#11" and "#11#1"
So just record it in map Record each string Number of occurrences , Then let the horizontal string And vertical string Is the multiplication of numbers .
（ Code as string It's more convenient , Compilation provides a pair of string Hash function of , If it is vector As map Of key, Also customize the hash , More trouble ）

class Solution {
    
public:
    int equalPairs(vector<vector<int>>& grid) {
    
        int m=grid.size(),n=grid[0].size();
        unordered_map<string,int> map_row;
        unordered_map<string,int> map_col;
        string row_str,col_str;
        for(int i=0;i<m;i++){
    
            row_str.clear();
            for(int j=0;j<n;j++){
    
                row_str+="#"+to_string(grid[i][j]);
            }
            map_row[row_str]++;
        }
        
        for(int i=0;i<n;i++){
    
            col_str.clear();
            for(int j=0;j<m;j++){
    
                col_str+="#"+to_string(grid[j][i]);
            }
            map_col[col_str]++;
        }
        int res=0;
        for(auto& it:map_row){
    
            if(map_col.count(it.first)){
    
                res+=it.second*map_col[it.first];
            }
        }
        return res;
        
        
    }
};