forked from Cyberavater/leetcode_practice
-
Notifications
You must be signed in to change notification settings - Fork 0
/
212. Word Search II.kt
78 lines (59 loc) · 1.94 KB
/
212. Word Search II.kt
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
class Trie {
val children = hashMapOf<Char, Trie>()
var tail = false
fun addWord(word: String) {
var cur = this
for (letter in word) {
if (letter !in cur.children) {
cur.children[letter] = Trie()
}
cur = cur.children[letter]!!
}
cur.tail = true
}
}
class Solution {
fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {
val trie = Trie()
for (word in words) {
trie.addWord(word)
}
val paths = hashSetOf<Pair<Int, Int>>()
val result = mutableListOf<String>()
val iSize = board.size
val jSize = board[0].size
var word = ""
fun dfs(path: Pair<Int, Int>, trieNode: Trie) {
if (path.first != -1
&& path.second != -1
&& path.first != iSize
&& path.second != jSize
) {
val letter = board[path.first][path.second]
if (path !in paths
&& letter in trieNode.children
) {
word += letter
val nextNode = trieNode.children[letter]!!
if (nextNode.tail) {
nextNode.tail = false
result.add(word)
}
paths.add(path)
dfs(Pair(path.first + 1, path.second), nextNode)
dfs(Pair(path.first - 1, path.second), nextNode)
dfs(Pair(path.first, path.second + 1), nextNode)
dfs(Pair(path.first, path.second - 1), nextNode)
paths.remove(path)
word = word.dropLast(1)
}
}
}
for (i in board.indices) {
for (j in board[0].indices) {
dfs(Pair(i, j), trie)
}
}
return result
}
}