a-063-word-search-ii2026-07-15hardleetcode #212neetcode150

단어 검색 II

#array#string#backtracking#trie#matrix

문제

· problem

P.a-063-word-search-ii

단어 검색 II

m × n 크기의 문자 보드와 문자열 목록이 주어졌을 때, 보드에 있는 모든 단어를 반환하세요. 각 단어는 인접한 셀(가로 또는 세로로 이웃한)의 문자로 순서대로 구성되어야 합니다. 같은 문자 셀을 한 단어에 두 번 이상 사용할 수 없습니다.

제약

· 1 ≤ m, n ≤ 12
· board[i][j] is a lowercase English letter
· 1 ≤ words.length ≤ 3 × 10⁴
· 1 ≤ words[i].length ≤ 10

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
["oath","pea","eat","rain"]

["eat","oath"]

example 2input → output

[["a","b"],["c","d"]]
["abcb"]

[]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
한 단어를 검색할 때 같은 셀을 두 번 이상 사용할 수 있나요?
☐
인접(adjacent)이란 상하좌우만 해당하나요, 대각선도 포함하나요?
☐
보드에서 한 단어가 여러 번 나타나면 여러 번 반환해야 하나요?
☐
Trie의 'refs' 카운터는 왜 필요한가요?
☐
단어를 찾은 후 'removeWord'를 호출하는 이유는?
☐
왜 대신 'isWord = False'만 설정하고 removeWord는 호출하지 않으면 안 되나요?
☐
DFS에서 4가지 방향 호출 순서가 중요한가요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· Trie에 모든 단어 추가

○

root.addWord(w)

○

words_set = set(words); word_dict = {w: True for w in words}

○

for w in sorted(words): root.addWord(w)

○

for w in words: root.addWord(w[::-1])

step 2· 검색 상태 초기화

○

res, visit = set(), set()

○

res, visit = [], set()

○

res, visit = set(), []

○

res, visit, found_words = set(), set(), set()

step 3· 경계 및 가지 제거 검사│ 중첩

○

or node.children[board[r][c]].refs < 1

○

or node.children[board[r][c]].refs == 0

○

or board[r][c] not in node.children

○

or len(node.children) == 0

step 4· 발견한 단어 제거 및 처리│ 중첩

○

root.removeWord(word)

○

node.isWord = False  # without removeWord

○

res.add(word); visit.clear()

○

res.discard(word)  # remove from result?

step 5· 모든 인접 셀 탐색│ 중첩

○

dfs(r + 1, c, node, word)

○

dfs(r + 1, c, node, word); dfs(r - 1, c, node, word)  # only vertical

○

dfs(r + 1, c + 1, node, word)  # diagonal

○

# only dfs(r + 1, c, node, word)

step 6· 상태 복원 (백트래킹)│ 중첩

○

visit.remove((r, c))

○

# no visit.remove — missing backtrack

○

visit = set()  # clear entire visited set

○

if (r, c) in visit: visit.remove((r, c))

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class TrieNode:

    def __init__(self):

        self.children = {}

        self.isWord = False

        self.refs = 0

    def addWord(self, word):

        cur = self

        cur.refs += 1

        for c in word:

            if c not in cur.children:

                cur.children[c] = TrieNode()

            cur = cur.children[c]

            cur.refs += 1

        cur.isWord = True

    def removeWord(self, word):

        cur = self

        cur.refs -= 1

        for c in word:

            if c in cur.children:

                cur = cur.children[c]

                cur.refs -= 1

class Solution:

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:

        root = TrieNode()

        for w in words:

            root.addWord(w)

        ROWS, COLS = len(board), len(board[0])

        res, visit = set(), set()

        def dfs(r, c, node, word):

            if (

                r not in range(ROWS)

                or c not in range(COLS)

                or board[r][c] not in node.children

                or node.children[board[r][c]].refs < 1

                or (r, c) in visit

):

                return

            visit.add((r, c))

            node = node.children[board[r][c]]

            word += board[r][c]

            if node.isWord:

                node.isWord = False

                res.add(word)

                root.removeWord(word)

            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))

        for r in range(ROWS):

            for c in range(COLS):

                dfs(r, c, root, "")

        return list(res)

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
["oath","pea","eat","rain"]

→

["eat","oath"]

case 2

[["a","b"],["c","d"]]
["abcb"]

→

[]

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.