(Leetcode) 212 - Word Search II (Trie, 트라이 문제)
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
주간 미션을 마쳤기 때문에 시간이 남아서 뒤 한문제를 골라 풀기로 하였다.
https://leetcode.com/problems/word-search-ii/
이 문제는 hard 문제이다. 쉽게 보고 도전했다가 역시 하드는 하드구나 느꼈다.
내가 작성한 풀이
처음에는 dfs로 풀만할 것 같아서 dfs로 접근하였다.
이 문제를 풀 때에는 이전에 갔던 경로로 다시 가지는 않는지도 체크해야 한다.
class Solution {
public List<String> findWords(char[][] board, String[] words) {
boolean[][] map = new boolean[board.length][board[0].length];
Set<String> contains = new HashSet<>();
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
for(String word : words) {
if(dfs(board, map, i, j, word, 0)) {
contains.add(word);
}
}
}
}
return contains.stream().toList();
}
public boolean dfs(char[][] board, boolean[][] map, int i, int j, String word, int index) {
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
return false;
}
if (board[i][j] != word.charAt(index)) {
return false;
}
if (map[i][j]) {
return false;
}
map[i][j] = true;
int next = index + 1;
if (next == word.length()) {
resetMap(map);
return true;
}
boolean result = dfs(board, map, i+1, j, word, next)
|| dfs(board, map, i-1, j, word, next)
|| dfs(board, map, i, j+1, word, next)
|| dfs(board, map, i, j-1, word, next);
if (!result) {
map[i][j] = false;
}
return result;
}
public void resetMap(boolean[][] map) {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
map[i][j] = false;
}
}
}
}
근데 이렇게 풀면 60번 예제 정도 되면 timeout 이 발생된다. 예를 들면 다음과 같은 input이 들어온다.
[["m","b","c","d","e","f","g","h","i","j","k","l"],
["n","a","a","a","a","a","a","a","a","a","a","a"],
["o","a","a","a","a","a","a","a","a","a","a","a"],
["p","a","a","a","a","a","a","a","a","a","a","a"],
["q","a","a","a","a","a","a","a","a","a","a","a"],
["r","a","a","a","a","a","a","a","a","a","a","a"],
["s","a","a","a","a","a","a","a","a","a","a","a"],
["t","a","a","a","a","a","a","a","a","a","a","a"],
["u","a","a","a","a","a","a","a","a","a","a","a"],
["v","a","a","a","a","a","a","a","a","a","a","a"],
["w","a","a","a","a","a","a","a","a","a","a","a"],
["x","y","z","a","a","a","a","a","a","a","a","a"]]
["aaaaaaaaaa","aaaaaaaaab","aaaaaaaaac","aaaaaaaaad",
"aaaaaaaaae","aaaaaaaaaf","aaaaaaaaag","aaaaaaaaah",
"aaaaaaaaai","aaaaaaaaaj","aaaaaaaaak","aaaaaaaaal",
"aaaaaaaaam","aaaaaaaaan","aaaaaaaaao","aaaaaaaaap",
"aaaaaaaaaq","aaaaaaaaar","aaaaaaaaas","aaaaaaaaat",
"aaaaaaaaau","aaaaaaaaav","aaaaaaaaaw","aaaaaaaaax",
"aaaaaaaaay","aaaaaaaaaz","aaaaaaaaba","aaaaaaaabb",
"aaaaaaaabc","aaaaaaaabd","aaaaaaaabe","aaaaaaaabf"...
TC, SC
- w : board width
- h : board height
- k : num of words
- l : length of word
이 풀이의 시간 복잡도는 O(w * h * k * l)이고, 공간 복잡도는 O(w * h + l)이다. TC와 SC를 계산해보니 무식하게 짜긴 했구나 느껴졌다.
모범 답안
trie 를 사용하여 해결한다. 사실 이 문제는 큐레이션에서 trie 로 분류되어 있긴 하다. 그럼에도 trie를 사용하지 않고 dfs로 먼저 시도해보았다. 하지만 dfs로는 아무리 개선해보려고 해도 시간 초과가 났다. (hacky 하게 해서 submit을 하긴 했지만…)
trie에 대해서 말로만 들어봤지 실제로 경험해 보는 것은 처음이였다.
class Solution {
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = buildTrie(words);
Set<String> contains = new HashSet<>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs(board, root, i, j, contains);
}
}
return contains.stream().toList();
}
public void dfs(char[][] board, TrieNode root, int i, int j, Set<String> contains) {
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
return;
}
char c = board[i][j];
if (c == '#' || root.children[c - 'a'] == null) {
return;
}
root = root.children[c - 'a'];
if (root.value != null) {
contains.add(root.value);
}
board[i][j] = '#';
dfs(board, root, i - 1, j, contains);
dfs(board, root, i, j - 1, contains);
dfs(board, root, i + 1, j, contains);
dfs(board, root, i, j + 1, contains);
board[i][j] = c;
}
public TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode current = root;
for (char letter : word.toCharArray()) {
int index = letter - 'a';
if (null == current.children[index]) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
current.value = word;
}
return root;
}
}
class TrieNode {
String value;
TrieNode[] children = new TrieNode[26];
}
재귀의 특성을 이용해 이미 지나간 곳은 임시로 ‘#’ 로 처리하여 중복 방문을 방지한 부분이 재밌는 부분이였던것 같다. 처리를 마치고 stack에서 해제될 때 다시 원래 값으로 복원해두도록 처리해두었다.
Node의 사이즈를 26으로 처리하여 알파벳 a-z를 커버한 부분도 재밌는 접근인 것 같다.
word가 중복 등록되는 것을 방지하고자 Set 자료구조를 사용하였다.
트라이 (Trie) 자료구조
발음에 유의해야 한다. (트리에 아님) 문자열 검색 및 자동완성, 사전 구현, 문자열 패턴 매칭, 접두사 검색, 데이터 압축 에 사용된다.
TC, SC
이 풀이의 시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다. 시간 복잡도가 O(n) 인 이유는 실제 DFS가 수행되는 시간은 단어의 총 길이에 비례하기 때문이다.