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.
Example 1:
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] Output: ["eat","oath"]
Example 2:
Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: []
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j]is a lowercase English letter.1 <= words.length <= 3 * 1041 <= words[i].length <= 10words[i]consists of lowercase English letters.- All the strings of
wordsare unique.
DFS.
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
def check(word):
cnt = Counter(word)
return all(counter[c] >= i for c, i in cnt.items())
def dfs(i, j, l, word):
if l == len(word):
return True
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[l]:
return False
c = board[i][j]
board[i][j] = '0'
ans = False
for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
x, y = i + a, j + b
ans = ans or dfs(x, y, l + 1, word)
board[i][j] = c
return ans
def find(word):
if not check(word):
return False
for i in range(m):
for j in range(n):
if dfs(i, j, 0, word):
return True
return False
m, n = len(board), len(board[0])
words = set(words)
counter = Counter(c for b in board for c in b)
return [word for word in words if find(word)]class Solution {
private int[] counter;
private char[][] board;
public List<String> findWords(char[][] board, String[] words) {
counter = new int[26];
this.board = board;
for (char[] b : board) {
for (char c : b) {
++counter[c - 'a'];
}
}
Set<String> s = new HashSet<>(Arrays.asList(words));
List<String> ans = new ArrayList<>();
for (String word : s) {
if (find(word)) {
ans.add(word);
}
}
return ans;
}
private boolean find(String word) {
if (!check(word)) {
return false;
}
for (int i = 0; i < board.length; ++i) {
for (int j = 0; j < board[0].length; ++j) {
if (dfs(i, j, 0, word)) {
return true;
}
}
}
return false;
}
private boolean dfs(int i, int j, int l, String word) {
if (l == word.length()) {
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(l)) {
return false;
}
char c = board[i][j];
board[i][j] = '0';
boolean ans = false;
int[] dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k];
int y = j + dirs[k + 1];
ans = ans || dfs(x, y, l + 1, word);
}
board[i][j] = c;
return ans;
}
private boolean check(String word) {
int[] cnt = new int[26];
for (char c : word.toCharArray()) {
++cnt[c - 'a'];
}
for (int i = 0; i < 26; ++i) {
if (counter[i] < cnt[i]) {
return false;
}
}
return true;
}
}class Solution {
public:
vector<int> counter;
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
counter.resize(26);
for (auto& b : board)
for (auto& c : b)
++counter[c - 'a'];
unordered_set<string> s(words.begin(), words.end());
vector<string> ans;
for (string word : s)
if (find(word, board))
ans.push_back(word);
return ans;
}
bool find(string& word, vector<vector<char>>& board) {
if (!check(word)) return false;
for (int i = 0; i < board.size(); ++i)
for (int j = 0; j < board[0].size(); ++j)
if (dfs(i, j, 0, word, board))
return true;
return false;
}
bool dfs(int i, int j, int l, string& word, vector<vector<char>>& board) {
if (l == word.size()) return true;
if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[l]) return false;
char c = board[i][j];
board[i][j] = '0';
bool ans = false;
vector<int> dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k)
{
int x = i + dirs[k], y = j + dirs[k + 1];
ans = ans || dfs(x, y, l + 1, word, board);
}
board[i][j] = c;
return ans;
}
bool check(string word) {
vector<int> cnt(26);
for (char c : word)
++cnt[c - 'a'];
for (int i = 0; i < 26; ++i)
if (counter[i] < cnt[i])
return false;
return true;
}
};func findWords(board [][]byte, words []string) []string {
counter := make([]int, 26)
for _, b := range board {
for _, c := range b {
counter[c-'a']++
}
}
s := make(map[string]bool)
for _, word := range words {
s[word] = true
}
check := func(word string) bool {
cnt := make([]int, 26)
for i := range word {
cnt[word[i]-'a']++
}
for i := 0; i < 26; i++ {
if counter[i] < cnt[i] {
return false
}
}
return true
}
var dfs func(i, j, l int, word string) bool
dfs = func(i, j, l int, word string) bool {
if l == len(word) {
return true
}
if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || board[i][j] != word[l] {
return false
}
c := board[i][j]
board[i][j] = '0'
ans := false
dirs := []int{-1, 0, 1, 0, -1}
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
ans = ans || dfs(x, y, l+1, word)
}
board[i][j] = c
return ans
}
find := func(word string) bool {
if !check(word) {
return false
}
for i, b := range board {
for j, _ := range b {
if dfs(i, j, 0, word) {
return true
}
}
}
return false
}
var ans []string
for word, _ := range s {
if find(word) {
ans = append(ans, word)
}
}
return ans
}