:orphan:

Word Search
===========

.. highlight:: none

Problem
-------
https://leetcode.com/problems/word-search/

Given an ``m x n`` grid of characters ``board`` and a string ``word``,
return ``true`` *if* ``word`` *exists in the grid*.

The word can be constructed from letters of sequentially adjacent cells,
where adjacent cells are horizontally or vertically neighboring. The
same letter cell may not be used more than once.

 

**Example 1:**

|image1|

::


   Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
   Output: true

**Example 2:**

|image2|

::


   Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
   Output: true

**Example 3:**

|image3|

::


   Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
   Output: false

 

**Constraints:**

- ``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.

 

**Follow up:** Could you use search pruning to make your solution faster
with a larger ``board``?

.. |image1| image:: https://assets.leetcode.com/uploads/2020/11/04/word2.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg
.. |image3| image:: https://assets.leetcode.com/uploads/2020/10/15/word3.jpg

.. highlight:: python

Pattern
-------
Array, String, Backtracking, Depth-First Search, Matrix

Approaches
----------

.. tab-set::

    .. tab-item:: Backtracking

        **Code**

        .. literalinclude:: ../problems/medium/word-search/word_search__backtracking.py
            :language: python
            :lines: 12-

        **Test**

        >>> from word_search__backtracking import exist
        >>> exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED")
        True
        >>> exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE")
        True
        >>> exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCB")
        False

        .. autofunction:: word_search__backtracking.exist