What is the best way to solve Word Search?

The optimized O(n) approach using Backtracking patterns is generally preferred.

상위 150개 인터뷰쉬움

단어 검색

'단어 검색' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

문자 보드의 m x n 그리드와 문자열 단어가 주어지면 그리드에 단어가 있으면 true를 반환합니다.

단어는 순차적으로 인접한 셀의 문자로 구성될 수 있으며, 인접한 셀은 수평 또는 수직으로 이웃합니다. 동일한 문자 셀은 두 번 이상 사용할 수 없습니다.

exist(board: list, word: str) -> bool 함수를 구현하세요.

제약

•m == board.length
•n == board[i].length
•1 <= m, n <= 6
•1 <= word.length <= 15
•board and word consists of only lowercase and uppercase English letters

예

Example 1

Input

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED"

Output

True

Explanation

The word ABCCED can be traced: A(0,0)->B(0,1)->C(0,2)->C(1,2)->E(2,2)->D(2,1).

Example 2

Input

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE"

Output

True

Explanation

The word SEE can be traced: S(1,3)->E(2,3)->E(2,2).

Example 3

Input

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCB"

Output

False

Explanation

Cannot trace ABCB without reusing cells.

Need a Hint?

세트 또는 힙과 같은 역추적 관련 데이터 구조를 사용하는 것이 좋습니다.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

역추적 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(n)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def exist_opt(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    path = set()
    def dfs(r, c, i):
        if i == len(word): return True
        if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != word[i] or (r, c) in path:
            return False
        path.add((r, c))
        res = dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1)
        path.remove((r, c))
        return res
    from collections import Counter
    count = Counter(word)
    board_count = Counter(char for row in board for char in row)
    for char in count:
        if count[char] > board_count[char]: return False
    if board_count[word[0]] > board_count[word[-1]]: word = word[::-1]
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0): return True
    return False

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def exist_brute(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    def dfs(r, c, i, visited):
        if i == len(word): return True
        if r < 0 or c < 0 or r >= rows or c >= cols or (r, c) in visited or board[r][c] != word[i]:
            return False
        visited.add((r, c))
        res = dfs(r + 1, c, i + 1, visited) or dfs(r - 1, c, i + 1, visited) or               dfs(r, c + 1, i + 1, visited) or dfs(r, c - 1, i + 1, visited)
        visited.remove((r, c))
        return res
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0, set()): return True
    return False