[Java] 212. Word Search II

문제 파악

문자가 채워져있는 m*n 크기의 보드가 주어진다.

 

문자열이 주어지는데, 해당 문자열을 만들 수 있으면 반환한다.

 

---

풀이

1️⃣ 백트래킹과 Set 이용한 풀이

💡 떠오른 Idea

백트래킹으로 만들 수 있는 문자열을 모두 구해본다. ( 최대 길이 10으로)

구한 문자열을 Set 에 넣고, 주어지는 문자열이 Set에 들어있는지 확인한다.

 

 

import java.util.*;

class Solution {
    int R;
    int C;
    boolean[][] checked;
    StringBuilder str = new StringBuilder();
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};
    char[][] board;
    Set<String> set = new HashSet<>();

    public List<String> findWords(char[][] board, String[] words) {
        List<String> ans = new ArrayList<>();
        this.board = board;
        R = board.length;
        C = board[0].length;
        checked = new boolean[R][C];
        
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                checked[r][c] = true;
                str.append(board[r][c]);
                search(r, c);
                str.deleteCharAt(0);
                checked[r][c] = false;
            }
        }


        for (String word : words) {
            if (set.contains(word)) {
                ans.add(word);
            }
        }
        return ans;
    }

    private void search(int r, int c) {

        set.add(str.toString());
        
        if (str.length() >= 10) {
            return;
        }


        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (0 <= nr && nr < R && 0 <= nc && nc < C && !checked[nr][nc]) {
                checked[nr][nc] = true;
                str.append(board[nr][nc]);
                search(nr, nc);
                checked[nr][nc] = false;
                str.deleteCharAt(str.length() - 1);
            }
        }
    }
}

 

결과

 

2️⃣ 백트래킹과 Trie 자료구조를 이용한 풀이

💡 떠오른 Idea

Trie 자료구조를 이용하면 시간을 개선할 수 있을 것이라 판단했다.

먼저, 찾아야 하는 문자열을 Trie 자료구조에 넣는다.

그리고, 백트래킹을 통해 문자열을 생성하는데, Trie 자료구조에 존재하는지 체크한다.

만약, 백트래킹을 통해 생성한 문자열이 접두어가 아니고 완전한 문자열이라면 정답 리스트에 추가해준다.

접두어로서 존재하지 않으면 백트래킹을 종료한다.

그리고, 완전한 문자열을 찾아 정답 리스트에 기록하는 경우 중복 방지를 위해 isEndOfWord 필드를 false로 변경해준다.

 

import java.util.*;

class Solution {
    int R;
    int C;
    boolean[][] checked;
    char[][] board;
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};
    Trie trie = new Trie();
    StringBuilder sb = new StringBuilder();
    List<String> ans = new ArrayList<>();

    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        R = board.length;
        C = board[0].length;
        checked = new boolean[R][C];

		// 찾아야 하는 문자열을 Trie 에 넣어준다.
        for (String word : words) {
            trie.insert(word);
        }

		// 각 시작점에서 만들 수 있는 모든 문자열을 탐색해본다.
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                checked[r][c] = true;
                sb.append(board[r][c]);
                bt(r, c, trie.root);
                checked[r][c] = false;
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        return ans;
    }

    public void bt(int r, int c, Node node) {
        char ch = board[r][c];
		
        // 지금까지 탐색해온 접두어를 갖는 문자가 Trie에 없는 경우
        if (!node.children.containsKey(ch)) {
            return;
        }

        Node child = node.children.get(ch);

		// 지금까지 탐색해온 문자열이 끝에 해당하는 문자인 경우 추가
        if (child.isEndOfWord) {
            ans.add(sb.toString());
            child.isEndOfWord = false;
        }

		// 백트래킹
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (0 <= nr && nr < R && 0 <= nc && nc < C && !checked[nr][nc]) {
                checked[nr][nc] = true;
                sb.append(board[nr][nc]);
                bt(nr, nc, child);
                checked[nr][nc] = false;
                sb.deleteCharAt(sb.length() - 1);

            }
        }

    }


}

// Trie 자료구조 구현
class Trie {
    Node root;

    public Trie() {
        this.root = new Node();
    }

    public void insert(String word) {
        insert(this.root, word);
    }

    private void insert(Node node, String word) {
        if (word.length() == 0) {
            node.isEndOfWord = true;
            return;
        }

        char ch = word.charAt(0);
        Node child;
        if (!node.children.containsKey(ch)) {
            child = new Node();
            node.children.put(ch, child);
        } else {
            child = node.children.get(ch);
        }

        insert(child, word.substring(1));

    }

    public boolean search(String word) {
        return search(this.root, word);
    }

    private boolean search(Node node, String word) {
        if (word.length() == 0) {
            return node.isEndOfWord;
        }

        char ch = word.charAt(0);

        if (!node.children.containsKey(ch)) {
            return false;
        }

        return search(node.children.get(ch), word.substring(1));
    }
}

class Node {
    Map<Character, Node> children;
    boolean isEndOfWord;

    public Node() {
        this.children = new HashMap<>();
        this.isEndOfWord = false;
    }
}

 

결과

 

---

📖 회고

 

처음에는, Set은 탐색 시 O(1) 로 할 수 있는데 이게 더 빠른 방법이 아닐까 했다.

 

하지만, Trie 를 이용하는 경우, 접두어에 해당하는 문자열이 존재하지 않는 경우 탐색을 바로 종료할 수 있어서 더 빠른 성능을 보였던 것 같다.

 

이런 문제를 보고 바로 Trie를 사용해야지 라는 생각을 떠올리는 것은 힘들 것 같긴하지만..ㅎ

 

Trie 관련 문제 3개를 풀면서 Trie 자료구조를 구현하는 방법은 확실하게 익힌 것 같다.

 

시간이 지나고 나서 이 문제를 다시 풀어보면 더욱 의미가 있을 것 같다.