LeetCode 212번: Word Search II(JAVA)
문제출처 212번: Word Search II
❔ 문제
String 배열 words의 각 단어 중 M*N char 배열 board에서 상하좌우로 연속된 문자열에 속한 단어를 출력.
⏩ 예시
Input: nboard = [[“o”,”a”,”a”,”n”],[“e”,”t”,”a”,”e”],[“i”,”h”,”k”,”r”],[“i”,”f”,”l”,”v”]],
words = [“oath”,”pea”,”eat”,”rain”]
Output: [“eat”,”oath”]
❕ 문제풀이
import java.util.*;
import java.util.stream.Collectors;
class Solution {
Set<String> result = new HashSet<>();
int[] dx = new int[]{0, 1, 0, -1};
int[] dy = new int[]{1, 0, -1, 0};
public List<String> findWords(char[][] board, String[] words) {
Trie trie = new Trie();
for (String word : words) { // 1.
trie.insert(trie.root, word.split(""), 0);
}
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) { // 2.
for (int j = 0; j < board[0].length; j++) {
visited[i][j] = true;
search(board, visited, i, j, trie.root);
visited[i][j] = false;
}
}
return new ArrayList<>(result);
}
public void search(char[][] board, boolean[][] visited, int x, int y, Node node) {
String s = String.valueOf(board[x][y]); // 현재 인덱스의 board 값
Node next = node.children.get(s); // 3.
if (next == null) return;
if (next.isEndOfWord) { // 4.
result.add(next.word);
}
for (int i = 0; i < 4; i++) { // 5.
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < visited.length && ny < visited[0].length && !visited[nx][ny]) {
visited[nx][ny] = true;
search(board, visited, nx, ny, next);
visited[nx][ny] = false;
}
}
}
class Trie {
Node root;
public Trie() {
this.root = new Node();
}
public void insert(Node node, String[] word, int idx) {
if (idx == word.length) {
node.isEndOfWord = true;
node.word = String.join("", word);
return;
}
String s = word[idx];
Node child = node.children.get(s);
if (child == null) {
child = new Node();
node.children.put(s, child);
}
insert(child, word, idx + 1);
}
}
class Node {
Map<String, Node> children;
boolean isEndOfWord;
String word;
public Node() {
this.children = new HashMap<>();
this.isEndOfWord = false;
}
}
}
- Trie 알고리즘을 이용하여 words 배열의 단어들을 트리에 포함시킨다.
- board의 각 단어에 대해 search(DFS 알고리즘)를 수행한다.
- 현재 board의 값이 Trie 트리의 자식에 속하면 프로세스를 진행한다.
- 만약 방금 찾은 자식의 노드가 단어의 끝이라면 해당 단어가 연속되어 포함된 것이므로 결과값에 추가한다.
- board의 상하좌우를 탐색하며 가능한 인덱스에 대해 다시 search를 시행한다.
💯 고찰
DFS와 Trie 알고리즘을 이용하여 문제를 해결하였다.
하지만 내가 푼 방식의 런타임시간과 공간복잡도가 상당히 비효율적이라는 결과가 나왔다.
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
TrieNode root = buildTrie(words);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs (board, i, j, root, res);
}
}
return res;
}
public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
char c = board[i][j];
if (c == '#' || p.next[c - 'a'] == null) return;
p = p.next[c - 'a'];
if (p.word != null) { // found one
res.add(p.word);
p.word = null; // de-duplicate
}
board[i][j] = '#';
if (i > 0) dfs(board, i - 1, j ,p, res);
if (j > 0) dfs(board, i, j - 1, p, res);
if (i < board.length - 1) dfs(board, i + 1, j, p, res);
if (j < board[0].length - 1) dfs(board, i, j + 1, p, res);
board[i][j] = c;
}
public TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode p = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (p.next[i] == null) p.next[i] = new TrieNode();
p = p.next[i];
}
p.word = w;
}
return root;
}
class TrieNode {
TrieNode[] next = new TrieNode[26];
String word;
}
해당 솔루션은 내가 풀이한 알고리즘의 방식들과는 차이가 없지만, 코드 최적화를 위한 여러 고민을 한 것으로 보인다.
- DFS시 불필요한 root(Trie 알고리즘에 있는)노드 호출을 제거.
chatAt()보다toChatArray()사용.- String 연산은
StringBuilder클래스 사용. - 문자의 끝을 알리는 boolean 대신 전체 문자를 저장하여
StringBuilder를 제거. - 추가적인 공간
boolean[][] visited대신 board의 문자를 “#”으로 잠시 변경하여 방문을 체크. - 알파벳 26개의 char 배열을 이용하여
HashSet을 제거. (알파벳에서 ‘a’코드값을 뺀 ASCII를 이용)
해당 문제를 풀이한 저자가 처음 쓰레기 코드에서 최적화를 통해 효율성이 좋은 코드로 변경하는 과정을 이렇게 기술하였다.
하나의 문제에도 더 나은 코드를 작성하기 위한 방법이 참신하게 많은 것 같다.
