Leetcode Word Search II problem solution

YASH PAL,

In this Leetcode Word Search II problem solution we have Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Leetcode Word Search II problem solution

Problem solution in Python.

class Node:
    def __init__(self, end = 0):
        self.end = end
        self.kids = {}

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        res, root, m, n = set(), Node(0), len(board), len(board[0])
        
        def setTrie(word):
            cur = root
            for w in word:
                if w not in cur.kids:
                    cur.kids[w] = Node()
                cur = cur.kids[w]
            cur.end = 1
            return
        
        def helper(i, j, root, visited, word):
            if root.end == 1: res.add(word)
            visited.add((i, j)) 

            for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                x, y = i + dx, j + dy
                if x < 0 or x >= m or y < 0 or y >= n or (x, y) in visited or board[x][y] not in root.kids: continue
                helper(x, y, root.kids[board[x][y]], visited, word + board[x][y])
            visited.remove((i, j))

            return        
        
        for word in words: setTrie(word)

        for i in range(m):
            for j in range(n):
                if board[i][j] in root.kids: helper(i, j, root.kids[board[i][j]], set(), board[i][j])         
                
        return list(res)

Problem solution in Java.

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String s : words) root.add(s, 0);
        Set<String> res = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                find(board, i, j, root.next[board[i][j] - 'a'], res);
            }
        }
        return new ArrayList<>(res);
    }
    
    private void find(char[][] board, int i, int j, TrieNode root, Set<String> res) {
        if (root == null) return;
        if (root.word != null) res.add(root.word);
        char c = board[i][j];
        board[i][j] = 'z' + 1;
        if (i > 0) find(board, i - 1, j, root.next[board[i - 1][j] - 'a'], res);
        if (j > 0) find(board, i, j - 1, root.next[board[i][j - 1] - 'a'], res);
        if (i < board.length - 1) find(board, i + 1, j, root.next[board[i + 1][j] - 'a'], res);
        if (j < board[0].length - 1) find(board, i, j + 1, root.next[board[i][j + 1] - 'a'], res);        
        board[i][j] = c;
    }
    
    class TrieNode {
        TrieNode[] next = new TrieNode[27];
        String word;
        public void add(String s, int index) {
            char c = s.charAt(index);
            if (next[c - 'a'] == null) next[c - 'a'] = new TrieNode();
            if (index + 1 < s.length()) next[c - 'a'].add(s, index + 1);
            else next[c - 'a'].word = s;
        }
    }
}

Problem solution in C++.

class Solution {
public:
    bool dfs(vector<vector<char>> &grid, int i, int j, int index, string &word)
    {
        if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size() || grid[i][j]!=word[index] || grid[i][j]=='*')
        return false;

        if(index==word.length()-1)
        return true;

        char c=grid[i][j];
        grid[i][j]='*';
        bool ans=false;

        if( dfs(grid, i+1 ,j ,index+1 ,word) ||
            dfs(grid, i-1 ,j ,index+1 ,word) || 
            dfs(grid, i ,j+1 ,index+1 ,word) || 
            dfs(grid, i ,j-1 ,index+1 ,word))
        ans=true;

        grid[i][j]=c;
        return ans;
    }
    
    vector<string> findWords(vector<vector<char>>& grid, vector<string>& word) {
        
        vector<string> ans;
        for(int a=0;a<word.size();a++) {
            for(int i=0;i<grid.size();i++) {
                int flag=0;
                for(int j=0;j<grid[0].size();j++) {
                    
                    if(word[a][0]==grid[i][j]) {
                        if(dfs(grid,i,j,0,word[a])) {
                            ans.push_back(word[a]);
                            flag=1;
                            break;
                        }
                    }
                }

                if(flag==1)
                break;
            }
        }
        
        return ans;
    }
};

coding problems