Simple Java Recursive Solution


  • 2
    M
    public int numIslands(char[][] grid) {
    
    		int height = grid.length;
    		if (height < 1)
    			return 0;
    		int width = grid[0].length;
    
    		boolean[][] check = new boolean[height][width];
    		int count = 0;
    		for (int i = 0; i < height; i++)
    			for (int j = 0; j < width; j++) {
    				if (grid[i][j] == '1' && !check[i][j]) {
    					count++;
    					numIslandsHelper(grid, check, i, j);
    				}
    			}
    
    		return count;
    
    	}
    
    	private void numIslandsHelper(char[][] grid, boolean[][] check, int i, int j) {
    
    		if (i < 0 || j < 0 || i > grid.length - 1 || j > grid[0].length - 1)
    			return;
    		if (grid[i][j] == '1' && !check[i][j])
    			check[i][j] = true;
    		else
    			return;
    		numIslandsHelper(grid, check, i, j + 1);
    		numIslandsHelper(grid, check, i, j - 1);
    		numIslandsHelper(grid, check, i + 1, j);
    		numIslandsHelper(grid, check, i - 1, j);
    
    	}

  • 0
    W

    I have implemented the same algorithm in C++, but it turns out to be TLE. I'm wondering why.

    Here is the code:

    class Solution {
    public:
    int count = 0;
    int row;
    int column;
    vector<vector<bool>> visit;

    void initVisit(int row, int column) {
        vector<bool> tmp;
        for(int j = 0; j < column; j++) {
            tmp.push_back(false);
        }
        for(int i = 0; i < row; i++) {
            visit.push_back(tmp);
        }
        return;
    }
    
    void helper(vector<vector<char>> grid, int i, int j) {
        if(i < 0 || j < 0 || i >= row || j >= column) return;
        if(visit[i][j]) return;    // has already been visited
        visit[i][j] = true;
        
        if(grid[i][j] == '1') {
            helper(grid, i - 1, j);
            helper(grid, i, j - 1);
            helper(grid, i + 1, j);
            helper(grid, i, j + 1);
        }
        
        
    }
    
    int numIslands(vector<vector<char>> grid) {
        row = grid.size();
        if(row == 0) return 0;
        column = grid[0].size();
        initVisit(row, column);
        
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < column; j++) {
                //cout <<"here:"<< i << j << visit[i][j] << endl; 
                if(!visit[i][j] && grid[i][j] == '1') {
                    helper(grid, i, j);
                    //cout << flag << endl;
                    count += 1;
                }
            }
        }
        return count;
        
        
    }
    

    };


  • 0
    M

    I don't see any problem with your code....Maybe OJ is more picky with C++...


  • 0
    W
    This post is deleted!

Log in to reply
 

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