Word Search II

Problem

Intuition: Since we have to find words (on the grid/board) present in words array by traversing in up/down/left/right fashion.
The traversal can be done using backtracking.
For searching of the word we can make use of trie, since this will also help us in early identification by checking if a prefix is present in the tree or not. This is to avoid un-necessary traversal of the board(i.e. no point in traversing the board, if the prefix is not present in the trie, then string or word form using the prefix will also not be present in the trie)

Approach: We will put all the words[] in the trie, then we will traverse the board for each cell(i,j) and will go in all the 4 directions to form various strings, and we will put all the strings that are present in the trie in a list.

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        int max = 0;
        Trie t = new Trie();
        for (String w : words) {
            t.insert(w);
        }

        int arr[][] = new int[board.length][board[0].length];
        StringBuilder str = new StringBuilder();

        Set<String> list = new HashSet<>();// to have only unique strings/words
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // recursively traverse all the cells to find the words
                traverse(i, j, board, arr, arr.length, arr[0].length, t, str, list);
            }
        }
        return new ArrayList<>(list);
    }

    public void traverse(int i, int j, char b[][], int arr[][], int n, int m, Trie t, StringBuilder str,Set<String> list) {

        str.append(b[i][j]);// add current cell character to form a potential prefix/word
        if (!t.startWith(str.toString())) {//early checking of prefix before moving forward to avoid un-necessary traversal
            str.deleteCharAt(str.length() - 1);
            return;
        }
        if (t.present(str.toString()))
            list.add(str.toString());

        arr[i][j] = 1;// mark current cell visited to avoid visiting the same cell the current recursive call stack

        int dirs[][] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };// left,right,up,down

        for (int dir[] : dirs) {
            int I = i + dir[0];
            int J = j + dir[1];
            if (I < n && J < m && I >= 0 && J >= 0 && arr[I][J] == 0) {
                traverse(I, J, b, arr, n, m, t, str, list);
            }
        }
        arr[i][j] =0;// mark unvisited 
        str.deleteCharAt(str.length()-1);// remove the last added character
    }

}

class Node {

    Node node[] = new Node[26];
    boolean flag;

    public boolean isPresent(char c) {
        return node[c - 'a'] != null;
    }

    public Node get(char c) {
        return node[c - 'a'];
    }

    public void add(char c, Node n) {
        node[c - 'a'] = n;
    }

    public void setFlag() {
        this.flag = true;
    }

    public boolean getFlag() {
        return this.flag;
    }
}

class Trie {
    Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String s) {
        Node node = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!node.isPresent(c)) {
                node.add(c, new Node());
            }
            node = node.get(c);
        }
        node.setFlag();
    }

    public boolean present(String s) {
        Node node = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!node.isPresent(c)) {
                return false;
            }
            node = node.get(c);
        }
        return node.getFlag();
    }

    public boolean startWith(String s) {
        Node node = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!node.isPresent(c)) {
                return false;
            }
            node = node.get(c);
        }
        return true;
    }
}

Blog

Prashant Mishra

Join Our Newsletter. No Spam, Only the good stuff.

Related