Reference: Problem I & Problem II
Difficulty: Medium

## Problem I

Given a 2D board and a word, find if the word exists in the grid.

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

Example:

Follow up: Reduce space complexity to $O(1)$.

## Analysis

### Backtracking

Consider how to write accept and reject base cases.

Can be optimized by setting board[i][j] ^= 256 and check if board[x][y] is less than 256. So we don’t need extra space.

Time: $O(MN \times 4^K)$ where $K$ is the length of the string.
Space: $O(MN)$

## Problem II

Marked

Use Trie.

https://leetcode.com/problems/word-search-ii/discuss/59780/Java-15ms-Easiest-Solution-(100.00)

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.