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.
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; } };
0 Comments