Need Help in Java code using dfs!!! Passing only 715/750 test cases.


  • 0
    A

    What I am doing is using dfs and the first coordinate from where dfs is called I'm appending 5 to a new string and for adjecent 1s I am appending string according to the index calculated from helper function. The test case in which code fails is too big to debug. Can anyone please find out what is wrong?
    Thanks in advance!

    class Solution {
        HashSet<String> hs = new HashSet<>();
        StringBuilder sb;
        int[] row = new int[]{1,-1,0,0};
        int[] col = new int[]{0,0,1,-1};
        public int numDistinctIslands(int[][] grid) {
            int r = grid.length, c = 0;
            if(r != 0){
                c = grid[0].length;
            }else{
                return 0;
            }
    
            boolean[][] visited = new boolean[r][c];
            for(int i=0;i<r;i++){
                for(int j=0;j<c;j++){
                    if(!visited[i][j] && grid[i][j] == 1){
                        visited[i][j] = true;
                        sb = new StringBuilder("5");
                        helper(grid,visited,i,j,r,c); 
                        hs.add(sb.toString());
                    }
                }
            }
    
        
            return hs.size();
        }
        
        public void helper(int[][] grid,boolean[][] visited, int i,int j,int r,int c){
    
            for(int k=0;k<4;k++){
                int m = i + row[k], n = j + col[k];
                if(m < r && n < c && m >= 0 && n >= 0 && !visited[m][n] && grid[m][n] == 1){
                    visited[m][n] = true;
                    sb.append(k);
                    helper(grid,visited,m,n,r,c);
                }
            }
        }
    }
    

  • 3
    D

    path itself doesn't unique identify a island, islands below will both have 50001 in your dfs.

    1111
    0001
    
    1111
    0010
    

    add node will work

        public void helper(int[][] grid,boolean[][] visited, int i,int j,int r,int c){
    
            for(int k=0;k<4;k++){
                int m = i + row[k], n = j + col[k];
                if(m < r && n < c && m >= 0 && n >= 0 && !visited[m][n] && grid[m][n] == 1){
                    visited[m][n] = true;
                    sb.append(k);
                    helper(grid,visited,m,n,r,c);
                }
            }
            sb.append("X");
        }
    

  • 0
    A

    Thanks for your help.
    The code works, but still, don't understand why it's working.
    This is sample input I have made to incorporate the example pointed out by you.
    [[1,1,1,1],[0,0,0,1],[0,0,0,0],[1,1,1,1],[0,0,1,0]]

    It is correctly giving 2 as output
    1 1 1 1
    0 0 0 1
    0 0 0 0
    1 1 1 1
    0 0 1 0

    The strings which get appended to the hashset are 52220 and 52202

    for(int i=0;i<r;i++){
                for(int j=0;j<c;j++){
                    if(!visited[i][j] && grid[i][j] == 1){
                        visited[i][j] = true;
                        sb = new StringBuilder("5");
                        helper(grid,visited,i,j,r,c); 
                        System.out.println(" sss " + sb.toString());
                        hs.add(sb.toString());
                    }
                }
            }
    

    Can you please point out any example in which different islands which generates same string?
    Thanks!


  • 1
    D

    @ashish53v said in Need Help in Java code using dfs!!! Passing only 715/750 test cases.:

    [[1,1,1,1],[0,0,0,1],[0,0,0,0],[1,1,1,1],[0,0,1,0]]

    i'm assuming traversing with order left, down, right, up, while you're traversing with order down, up, left, right, check this case:
    [[1,0,0,1,0],[1,0,0,1,0],[1,0,0,1,1],[1,1,0,1,0]]


  • 0
    A

    @D3Hunter said in Need Help in Java code using dfs!!! Passing only 715/750 test cases.:

    [[1,0,0,1,0],[1,0,0,1,0],[1,0,0,1,1],[1,1,0,1,0]]

    yes, it worked.... thanks again..cheers!!!


Log in to reply
 

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