Java solution DFS iteration no recursion


  • 0
    L

    This is a DFS iteration solution with modify input grid[][] :

    public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) {
    			return 0;
    		}
    		int m = grid.length; 
    		int n = grid[0].length;
    		int count = 0;
    		for (int i = 0; i < m; i ++) {
    			for (int j = 0; j < n; j ++) {
    				if (grid[i][j] == '1') {
    					Stack<Cord> s = new Stack<>();
    					s.push(new Cord(i, j));
    					while (!s.isEmpty()) {
    						Cord cur = s.pop();
    						pushToS(cur._x - 1, cur._y, grid, s);
    						pushToS(cur._x, cur._y + 1, grid, s);
    						pushToS(cur._x + 1, cur._y, grid, s);
    						pushToS(cur._x, cur._y - 1, grid, s);
    					}
    					count ++;
    				}
    			}
    		}
    		return count;
        }
    	
    	private void pushToS(int i, int j, char[][] grid, Stack<Cord> s) {
    		if( i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] !='1') {
    			return;
    		}
    		grid[i][j] = '0';
    		Cord temp = new Cord(i, j);
    		s.push(temp);
    	}
    	
    	private class Cord {
    		int _x;
    		int _y;
    		public Cord (int x, int y) {
    			_x = x;
    			_y = y;
    		}
    	}
    

    This is actually a graph, if we are not allowed to edit input we need to use set.
    Correct Way to do this :
    This is a DFS iteration solution without modify input grid[][] using set ,
    TLM in leetcode, but if we don't write pushToS function, it will pass. (the testcase in leetcode is too small)

    public int numIslands(char[][] grid) {
    		if (grid == null || grid.length == 0 || grid[0].length == 0) {
    			return 0;
    		}
    		int m = grid.length; 
    		int n = grid[0].length;
    		int count = 0;
    		Set<Cord> set = new HashSet<>();
    		for (int i = 0; i < m; i ++) {
    			for (int j = 0; j < n; j ++) {
    				if (grid[i][j] == '1') {
    					Cord cord = new Cord(i, j);
    					if (!set.contains(cord)) {
    						Stack<Cord> s = new Stack<>();
    						s.push(cord);
    						set.add(cord);
    						while (!s.isEmpty()) {
    							Cord cur = s.pop();
    							int x = cur._x;
    							int y = cur._y;
    							pushToS(x - 1, y, grid, s, set);
    							pushToS(x, y + 1, grid, s, set);
    							pushToS(x + 1, y, grid, s, set);
    							pushToS(x, y - 1, grid, s, set);
    						}
    						count ++;
    					}
    				}
    			}
    		}
    		return count;
        }
    	
    	private void pushToS(int i, int j, char[][] grid, Stack<Cord> s, Set<Cord> set) {
    		if( i < 0 || i > grid.length || j < 0 || j >= grid[0].length || grid[i][j] !='1' || set.contains(new Cord(i, j))) {
    			return;
    		}
    		Cord temp = new Cord(i, j);
    		s.add(temp);
    		set.add(temp);
    	}
    	
    	private class Cord {
    		int _x;
    		int _y;
    		public Cord (int x, int y) {
    			_x = x;
    			_y = y;
    		}
    		@Override
    		public boolean equals (Object that) {
    			return (that != null && that instanceof Cord && 
    					((Cord) that)._x == _x && ((Cord) that)._y == _y);
    		}
    		
    		@Override
    		public int hashCode () {
    			return _x + _y;
    		}
    	}
    

Log in to reply
 

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