DEV Community

Cover image for 79. Word Search
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

1

79. Word Search

79. Word Search

Medium

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:

word2

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

Example 2:

word-1

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

Example 3:

word3

  • 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?

Solution:

class Solution {

    /**
     * @param String[][] $board
     * @param String $word
     * @return Boolean
     */
    function exist($board, $word) {
        for ($i = 0; $i < count($board); ++$i)
            for ($j = 0; $j < count($board[0]); ++$j)
                if ($this->dfs($board, $word, $i, $j, 0))
                    return true;
        return false;
    }

    private function dfs($board, $word, $i, $j, $s)
    {
        if ($i < 0 || $i == count($board) || $j < 0 || $j == count($board[0]))
            return false;
        if ($board[$i][$j] != $word[$s] || $board[$i][$j] == '*')
            return false;
        if ($s == strlen($word) - 1)
            return true;

        $cache = $board[$i][$j];
        $board[$i][$j] = '*';
        $isExist = $this->dfs($board, $word, $i + 1, $j, $s + 1) ||
            $this->dfs($board, $word, $i - 1, $j, $s + 1) ||
            $this->dfs($board, $word, $i, $j + 1, $s + 1) ||
            $this->dfs($board, $word, $i, $j - 1, $s + 1);
        $board[$i][$j] = $cache;

        return $isExist;
    }

}
Enter fullscreen mode Exit fullscreen mode

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

Billboard image

Use Playwright to test. Use Playwright to monitor.

Join Vercel, CrowdStrike, and thousands of other teams that run end-to-end monitors on Checkly's programmable monitoring platform.

Get started now!

Top comments (0)

Image of AssemblyAI

Automatic Speech Recognition with AssemblyAI

Experience near-human accuracy, low-latency performance, and advanced Speech AI capabilities with AssemblyAI's Speech-to-Text API. Sign up today and get $50 in API credit. No credit card required.

Try the API

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay