-
Notifications
You must be signed in to change notification settings - Fork 14
/
WordSearch_IIUsingRecursion.java
121 lines (104 loc) · 3.39 KB
/
WordSearch_IIUsingRecursion.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
package by.andd3dfx.search.wordsearch;
import lombok.AllArgsConstructor;
import lombok.Data;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;
/**
* <pre>
* <a href="https://leetcode.com/problems/word-search-ii/">Task description</a>
*
* 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: []
* </pre>
*
* @see <a href="https://youtu.be/DTyMyr6bNGw">Video solution</a>
*/
public class WordSearch_IIUsingRecursion implements IWordSearch_II {
private long recursionCallCounter = 0L;
@Data
@AllArgsConstructor
public static class Context {
private char[][] board;
private Set<String> wordsToFind;
private int maxLen;
private Set<String> wordsFound;
public int m() {
return board.length;
}
public int n() {
return board[0].length;
}
}
@Override
public List<String> findWords(char[][] board, String[] words) {
var wordsToFind = Arrays.stream(words).collect(Collectors.toSet());
int maxLen = Arrays.stream(words)
.map(String::length)
.max(Integer::compareTo)
.orElse(-1);
var resultWordsSet = new HashSet<String>();
var ctx = new Context(board, wordsToFind, maxLen, resultWordsSet);
for (int i = 0; i < ctx.m(); i++) {
for (int j = 0; j < ctx.n(); j++) {
var visited = new boolean[ctx.m()][ctx.n()];
examine(i, j, "", visited, ctx);
}
}
System.out.println(recursionCallCounter);
return resultWordsSet.stream().toList();
}
public void examine(int i, int j, String str, boolean[][] visited, Context ctx) {
recursionCallCounter++;
if (i < 0 || j < 0 || i >= ctx.m() || j >= ctx.n()) {
return;
}
if (visited[i][j] || str.length() >= ctx.maxLen) {
return;
}
if (allWordsToFindAreNotStartedWithPrefix(ctx.wordsToFind, str)) {
return;
}
visited[i][j] = true;
str += ctx.board[i][j];
if (ctx.wordsToFind.contains(str)) {
ctx.wordsFound.add(str);
ctx.wordsToFind.remove(str);
}
examine(i - 1, j, str, visited, ctx);
examine(i + 1, j, str, visited, ctx);
examine(i, j - 1, str, visited, ctx);
examine(i, j + 1, str, visited, ctx);
visited[i][j] = false;
}
private boolean allWordsToFindAreNotStartedWithPrefix(Set<String> wordsToFind, String prefix) {
for (var word : wordsToFind) {
if (word.startsWith(prefix)) {
return false;
}
}
return true;
}
}