212. Word Search II

212. Word Search II

 

Hint 1

 

You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?

 

 

Hint 2

 

If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: Implement Trie (Prefix Tree) first.

 

 

 

 

https://leetcode.com/problems/implement-trie-prefix-tree/description/ : 208. Implement Trie (Prefix Tree)

 

https://youtu.be/asbcE9mZz_U?si=7ovXqcPW-mJDtg7h

 

 

 

class TrieNode:
    def __init__(self):
        self.children = {}  # 자식 노드를 저장하는 딕셔너리 (예: {'a': TrieNode()})
        self.isWord = False  # 현재 노드가 단어의 끝인지 여부를 나타내는 플래그

    def addWord(self, word):
        cur = self  # 현재 노드에서 시작
        for c in word:
            if c not in cur.children:  # 현재 문자가 자식 노드에 없으면
                cur.children[c] = TrieNode()  # 새 TrieNode 생성 후 추가
            cur = cur.children[c]  # 현재 노드를 자식 노드로 이동
        cur.isWord = True  # 단어 끝 노드에 isWord를 True로 설정


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()  # Trie의 루트 노드 생성

        # 주어진 words를 Trie에 추가
        for w in words:
            root.addWord(w)

        # 보드 정보 가져오기
        ROWS, COLS = len(board), len(board[0])  # 보드의 행과 열 크기
        res, visit = set(), set()  # 결과를 저장할 집합과 방문한 셀 추적을 위한 집합 초기화

        # DFS 탐색 함수 정의
        def dfs(r, c, node, word):
            # base case: 탐색을 종료할 조건
            if (r < 0 or c < 0 or  # 보드의 경계를 벗어난 경우
                r == ROWS or c == COLS or  # 보드의 끝을 초과한 경우
                (r, c) in visit or  # 이미 방문한 셀인 경우
                board[r][c] not in node.children):  # 현재 문자가 트라이에 없는 경우
                return
            
            # 현재 셀을 방문했다고 표시
            visit.add((r, c))

            # 현재 노드 갱신 및 단어에 문자 추가
            node = node.children[board[r][c]]  # 현재 문자의 자식 노드로 이동
            word += board[r][c]  # 현재 문자를 단어에 추가

            if node.isWord:  # 현재 노드가 단어의 끝이면
                res.add(word)  # 결과 집합에 단어 추가

            # 4방향으로 DFS 탐색
            dfs(r - 1, c, node, word)  # 위쪽 셀 탐색
            dfs(r + 1, c, node, word)  # 아래쪽 셀 탐색
            dfs(r, c - 1, node, word)  # 왼쪽 셀 탐색
            dfs(r, c + 1, node, word)  # 오른쪽 셀 탐색

            # 탐색이 끝난 후 방문 표시를 해제 (백트래킹)
            visit.remove((r, c))

        # 보드의 모든 셀에서 DFS 시작
        for r in range(ROWS):  # 보드의 각 행에 대해 반복
            for c in range(COLS):  # 각 열에 대해 반복
                dfs(r, c, root, "")  # DFS 호출, 초기 단어는 빈 문자열

        return list(res)  # 결과를 리스트로 변환하여 반환

 

한글 주석 설명

• TrieNode 클래스:
  • Trie 자료구조의 각 노드를 정의하며, 자식 노드와 단어의 끝임을 나타내는 플래그를 가집니다.
  • addWord 메서드는 트라이에 단어를 추가하는 역할을 합니다.
• Solution 클래스:
  • findWords 메서드는 주어진 보드와 단어 리스트에서 존재하는 단어를 찾는 메인 함수입니다.
  • dfs 함수는 재귀적으로 보드의 셀을 탐색하며 가능한 단어를 구성합니다.
  • 탐색 종료 조건(base case)과 백트래킹을 통해 방문 상태를 관리합니다.
• 각 줄마다 세부적으로 설명해, 코드의 흐름과 로직이 명확하도록 주석을 추가했습니다.

 

GPT 풀이

트라이(Trie) 자료구조와 백트래킹(Backtracking)을 조합해서 효율적으로 풀 수 있습니다. 이 문제를 푸는 핵심은:

1. Trie 자료구조: words 리스트를 효율적으로 탐색하기 위해 트라이를 사용합니다.
2. 백트래킹: 보드의 각 위치에서 시작하여 가능한 단어를 탐색합니다.
3. 중복 사용 방지: 같은 셀을 두 번 사용할 수 없도록 방문한 셀을 추적합니다.

아래는 단계별로 풀이하는 방법과 구현 코드입니다.

---

풀이 전략

1. 트라이에 단어 삽입:
   • words 리스트에 있는 모든 단어를 트라이에 삽입합니다.
   • 각 노드는 현재까지의 접두사를 나타내며, 단어의 끝을 표시하는 플래그를 추가합니다.
2. 보드에서 백트래킹:
   • 보드의 각 셀에서 탐색을 시작합니다.
   • 현재 셀의 문자가 트라이에 있는지 확인하고, 있다면 다음 방향으로 재귀적으로 탐색합니다.
   • 이미 방문한 셀은 다시 탐색하지 않도록 추적합니다.
3. 종료 조건:
   • 현재 노드가 트라이의 단어 끝을 나타내는 경우 결과에 추가합니다.
   • 유효하지 않은 경로는 탐색을 종료합니다.

class TrieNode:
    def __init__(self):
        self.children = {}  # 자식 노드들
        self.word = None  # 노드에서 끝나는 단어 (있다면 저장)

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.word = word  # 단어 끝에 단어 저장


class Solution:
    def findWords(self, board, words):
        # 1. Trie에 단어 삽입
        trie = Trie()
        for word in words:
            trie.insert(word)
        
        # 2. 결과를 저장할 집합 (중복 방지)
        result = set()
        rows, cols = len(board), len(board[0])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 우, 하, 좌, 상 방향
        
        # 3. DFS 백트래킹 함수
        def backtrack(r, c, node):
            if board[r][c] not in node.children:  # 현재 문자가 트라이에 없으면 종료
                return
            
            char = board[r][c]
            next_node = node.children[char]
            
            if next_node.word:  # 현재 노드에서 끝나는 단어가 있으면 결과에 추가
                result.add(next_node.word)
            
            # 방문 처리
            board[r][c] = "#"  # 방문한 셀 표시
            
            # 4방향 탐색
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                    backtrack(nr, nc, next_node)
            
            # 방문 처리 복구
            board[r][c] = char
        
        # 4. 보드의 모든 셀에서 탐색 시작
        for r in range(rows):
            for c in range(cols):
                backtrack(r, c, trie.root)
        
        return list(result)

# 사용 예시
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath", "pea", "eat", "rain"]
solution = Solution()
print(solution.findWords(board, words))  # Output: ["eat", "oath"]

 

코드 설명

1. Trie 자료구조:
   • Trie 클래스는 insert 메서드를 통해 단어를 삽입합니다.
   • 각 단어의 마지막 문자 노드에 word 값을 저장해 단어의 끝을 표시합니다.
2. DFS 백트래킹:
   • 보드의 각 셀에서 시작하여 트라이에 저장된 단어를 찾습니다.
   • 방문한 셀은 "#"로 표시해 재방문을 방지합니다.
   • 탐색이 끝난 후 원래 문자를 복구합니다.
3. 결과 저장:
   • result는 집합(set)을 사용해 중복된 단어를 방지합니다.
   • 탐색이 끝난 후 리스트로 반환합니다.