https://leetcode.com/problems/word-search-ii/?envType=study-plan-v2&envId=top-interview-150

212. Word Search II

⭐ 문제

주어진 문자로 구성된 m x n 보드와 문자열 리스트 words가 있을 때, 보드에서 찾을 수 있는 모든 단어를 반환하세요

각 단어는 수평 또는 수직으로 이웃한 셀들의 문자로 구성되어야 합니다. 동일한 문자 셀은 단어 안에서 한 번 이상 사용될 수 없습니다.

Example

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"]

🤔 접근 방향

보드에서 단어를 찾는 과정은 보드의 특정 셀에서 시작하여 인접한 셀로 이동하며 단어를 형성하는 과정으로, 이는 깊이 우선 탐색(DFS)으로 모델링할 수 있습니다. DFS는 가능한 모든 경로를 탐색하면서 단어를 찾는 데 효과적입니다.
또한 문자열 검색과 관련된 작업을 효율적으로 수행하기 위해 Trie 자료구조를 사용합니다. 단어 목록을 Trie에 저장하면 접두사 검사를 빠르게 수행할 수 있으며, 보드에서 문자를 검색하면서 Trie를 사용하여 현재까지 찾은 문자열이 Trie 내에 있는지 확인할 수 있습니다. 이를 통해 불필요한 탐색을 줄이고 효율적으로 단어를 찾을 수 있습니다.

• Trie 클래스는 단어 목록을 저장하는 자료구조로 사용됩니다. insert 메서드는 단어를 Trie에 삽입합니다. 각 문자를 Trie에 삽입하면서 단어의 끝을 나타내는 노드의 변수를 설정합니다.

• dfs 메서드는 깊이 우선 탐색(DFS)을 수행합니다. DFS를 재귀적으로 호출하여 인접한 셀로 이동하며 단어를 계속 형성하고 검색합니다. 만약 현재 문자열을 찾으면, 결과 집합에 해당 단어를 추가하고 Trie에서 해당 단어를 표시하는 노드를 false로 설정하여 중복을 방지합니다.

• findWords 메서드는 주어진 보드와 단어 목록을 사용하여 모든 단어를 찾는 역할을 합니다. 먼저 Trie 자료구조를 초기화하고, 단어 목록을 Trie에 삽입합니다. 그런 다음 보드의 각 셀을 순회하며 DFS를 호출하여 가능한 모든 단어를 찾습니다.

✍️ 의사 코드

클래스 Trie:
    노드 클래스 TrieNode:
        TrieNode 배열 children
        boolean isEnd

    TrieNode 생성자:
        children 배열 초기화
        isEnd를 False로 초기화

    Trie 생성자:
        루트 노드 초기화

    함수 insert(단어):
        현재 노드를 루트로 설정
        단어의 각 문자를 반복:
            문자를 인덱스로 변환
            현재 노드의 children 배열에서 해당 인덱스의 노드가 없으면:
                해당 인덱스에 새로운 노드를 생성하고 연결
            현재 노드를 해당 인덱스의 노드로 업데이트
        현재 노드의 isEnd를 True로 설정

클래스 Solution:
    함수 findWords(보드, 단어목록):
        Trie를 생성하여 초기화
        단어목록의 각 단어를 Trie에 삽입

        결과 집합 result 초기화

        보드의 행 수(m)와 열 수(n)를 얻기

        각 행 i를 반복:
            각 열 j를 반복:
                dfs 함수를 호출하여 현재 위치에서 시작
                dfs 함수에서 반환된 결과를 result에 추가

        결과 집합을 List로 변환하여 반환

✅ 나의 풀이

class TrieNode {
    TrieNode[] children;
    boolean isEnd;

    public TrieNode() {
        children = new TrieNode[26];
        isEnd = false;
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
}

public class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }

        Set<String> result = new HashSet<>();
        int m = board.length;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, trie.root, "", result);
            }
        }

        return new ArrayList<>(result);
    }

    private void dfs(char[][] board, int x, int y, TrieNode node, String current, Set<String> result) {
        char ch = board[x][y];
        int index = ch - 'a';

        if (ch == '#' || node.children[index] == null) {
            return;
        }

        current += ch;
        TrieNode nextNode = node.children[index];

        if (nextNode.isEnd) {
            result.add(current);
            nextNode.isEnd = false; 
        }

        board[x][y] = '#'; 

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (newX >= 0 && newX < board.length && newY >= 0 && newY < board[0].length) {
                dfs(board, newX, newY, nextNode, current, result);
            }
        }

        board[x][y] = ch; 
    }
}

🖥️ 결과

Runtime: 464 ms
Memory Usage: 46.8 MB