Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //DFS solution
- //Time: O(m * n * output)
- //Space: O(output) for call stack
- class Solution {
- public int numIslands(char[][] grid) {
- int ans = 0;
- for(int i = 0; i < grid.length; i++) {
- for(int j = 0; j < grid[0].length; j++) {
- if(grid[i][j] == '1') {
- ans++;
- deleteIsland(grid, i, j);
- }
- }
- }
- return ans;
- }
- private void deleteIsland(char[][] grid, int i, int j) {
- if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
- return;
- }
- grid[i][j] = '0';
- deleteIsland(grid, i - 1, j);
- deleteIsland(grid, i, j - 1);
- deleteIsland(grid, i + 1, j);
- deleteIsland(grid, i, j + 1);
- }
- }
Add Comment
Please, Sign In to add comment