Word Search in a Grid

Word Search in a grid

Given m x n matrix which contains all letters and a list of words Find all the words in the grid, A word in a grid can be adjacent cell horizontally or vertically

From above grid, word can be found: chin, chino If chino is in a given dictionary, then the reverse of chino is also can be found in the grid

Word	Reverse word
chin	reverse of chin
chino	reverse of chino

$b/java/WordSearch.java

    // For h, w location
    public static void wordSearch(char[][] arr,  int h, int w, String s, Set set, Set dict){
        int height = arr.length;
        int width = arr[0].length;
        
        char c = arr[h][w];
        if(c != '0'){
            arr[h][w] = '0';
            String ss = s + (c + "");

            if(dict.contains(ss)){
               set.add(ss); 
            }

            if(h + 1 < height){
                wordSearch(arr, h + 1, w, ss, set, dict);
            }

            if(h - 1 >= 0){
                wordSearch(arr, h - 1, w, ss, set, dict);
            }

            if(w - 1 >= 0){
                wordSearch(arr, h, w - 1, ss, set, dict);
            }

            if(w + 1 < width){
                wordSearch(arr, h, w + 1, ss, set, dict);
            }

            arr[h][w] = c;
        }
    }

    // For height x width all elements
    public static Set wordSearchAll(char[][] arr, Set dict){
        int height = arr.length;
        int width = arr[0].length;
        String ss = "";
        Set set = new HashSet<>();

        dict.add("k");
        dict.add("kecccb");
        dict.add("kecccbabc");
        dict.add("a");
        dict.add("ab");
        dict.add("abk");
        dict.add("abke");
        dict.add("abcccecbk");

        dict.add("abb");
        dict.add("akc");


        // char[][] arr = {
            // {'a', 'b', 'c'},
            // {'b', 'k', 'c'},
            // {'c', 'e', 'c'}
        // };

        for(int h = 0; h < height; h++){
            for(int w = 0; w < width; w++){
                wordSearch(arr, h, w, ss, set, dict);
            }
        }
        pl(set);
        return set;
    }

How the problem is related to Connection Island problem

The two problems are almost same. Essentially, they are both graph problems. Given a graph, find all the paths from a given node

Find all paths from a root in a given Binary Tree

      public static void printAllPath(Node r, List ls){
        if(r != null){
            if(r.left == null && r.right == null){
                printList(append(ls, r.data));
            }else{
                printAllPath(r.left,  append(ls, r.data));
                printAllPath(r.right, append(ls, r.data));
            }
            
        }
    }