Clean recursive C++ solution by creating unique string based on turn taken


  • 1
    A
    class Solution {
    public:
        // we need the depth to differentiate between [[1,0],[1,1],[1,0]] (dddr) and [1,0],[1,0],[1,1] (dddr) 
        void colorIsland(vector<vector<int>>& grid, int i, int j, int color, string &x, int d) {
            if(!grid[i][j]) {
                return;
            }
            x += to_string(d);
            grid[i][j] = color;
            if(i < grid.size() - 1 && grid[i+1][j] == 1){
                x = x + "d";
                colorIsland(grid, i+1, j, color, x, d+1);
            }
            if(i > 0 && grid[i-1][j] == 1) {
                x = x + "u";
                colorIsland(grid, i-1, j, color, x, d+1);
            }
            if(j < grid[i].size() - 1 && grid[i][j+1] == 1){
                x = x + "r";
                colorIsland(grid, i, j+1, color, x, d+1);
            }
            if(j > 0 && grid[i][j-1] == 1) {
                x = x + "l";
                colorIsland(grid, i, j-1, color, x, d+1);
            }
        }
    
        int numDistinctIslands(vector<vector<int>>& grid) {
            int count = 0;
            unordered_set<string> shape;
            for(int i=0; i<grid.size(); i++) {
                for(int j=0; j<grid[i].size(); j++) {
                    if(grid[i][j] == 1) {
                        string x;
                        colorIsland(grid, i, j, 2, x, 0);
                        if(shape.find(x) == shape.end()) {
                            shape.insert(x);
                            count++;
                        }
                    }
                }
            }
            return count;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.