bowang0911/leetcode huggingface dataset:
N-Queens

The **n-queens** puzzle is the problem of placing `n` queens on an `n x n` chessboard such that no two queens attack each other.

Given an integer `n`, return _all distinct solutions to the **n-queens puzzle**_. You may return the answer in **any order**.

Each solution contains a distinct board configuration of the n-queens' placement, where `'Q'` and `'.'` both indicate a queen and an empty space, respectively.

**Example 1:**

**Input:** n = 4
**Output:** \[\[ ".Q.. ", "...Q ", "Q... ", "..Q. "\],\[ "..Q. ", "Q... ", "...Q ", ".Q.. "\]\]
**Explanation:** There exist two distinct solutions to the 4-queens puzzle as shown above

**Example 2:**

**Input:** n = 1
**Output:** \[\[ "Q "\]\]

**Constraints:**

*   `1 <= n <= 9`
N-Queens II

The **n-queens** puzzle is the problem of placing `n` queens on an `n x n` chessboard such that no two queens attack each other.

Given an integer `n`, return _the number of distinct solutions to the **n-queens puzzle**_.

**Example 1:**

**Input:** n = 4
**Output:** 2
**Explanation:** There are two distinct solutions to the 4-queens puzzle as shown.

**Example 2:**

**Input:** n = 1
**Output:** 1

**Constraints:**

*   `1 <= n <= 9`
Maximum Subarray

Given an integer array `nums`, find the subarray with the largest sum, and return _its sum_.

**Example 1:**

**Input:** nums = \[-2,1,-3,4,-1,2,1,-5,4\]
**Output:** 6
**Explanation:** The subarray \[4,-1,2,1\] has the largest sum 6.

**Example 2:**

**Input:** nums = \[1\]
**Output:** 1
**Explanation:** The subarray \[1\] has the largest sum 1.

**Example 3:**

**Input:** nums = \[5,4,-1,7,8\]
**Output:** 23
**Explanation:** The subarray \[5,4,-1,7,8\] has the largest sum 23.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-104 <= nums[i] <= 104`

**Follow up:** If you have figured out the `O(n)` solution, try coding another solution using the **divide and conquer** approach, which is more subtle.
Spiral Matrix

Given an `m x n` `matrix`, return _all elements of the_ `matrix` _in spiral order_.

**Example 1:**

**Input:** matrix = \[\[1,2,3\],\[4,5,6\],\[7,8,9\]\]
**Output:** \[1,2,3,6,9,8,7,4,5\]

**Example 2:**

**Input:** matrix = \[\[1,2,3,4\],\[5,6,7,8\],\[9,10,11,12\]\]
**Output:** \[1,2,3,4,8,12,11,10,9,5,6,7\]

**Constraints:**

*   `m == matrix.length`
*   `n == matrix[i].length`
*   `1 <= m, n <= 10`
*   `-100 <= matrix[i][j] <= 100`
Jump Game

You are given an integer array `nums`. You are initially positioned at the array's **first index**, and each element in the array represents your maximum jump length at that position.

Return `true` _if you can reach the last index, or_ `false` _otherwise_.

**Example 1:**

**Input:** nums = \[2,3,1,1,4\]
**Output:** true
**Explanation:** Jump 1 step from index 0 to 1, then 3 steps to the last index.

**Example 2:**

**Input:** nums = \[3,2,1,0,4\]
**Output:** false
**Explanation:** You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

**Constraints:**

*   `1 <= nums.length <= 104`
*   `0 <= nums[i] <= 105`
Merge Intervals

Given an array of `intervals` where `intervals[i] = [starti, endi]`, merge all overlapping intervals, and return _an array of the non-overlapping intervals that cover all the intervals in the input_.

**Example 1:**

**Input:** intervals = \[\[1,3\],\[2,6\],\[8,10\],\[15,18\]\]
**Output:** \[\[1,6\],\[8,10\],\[15,18\]\]
**Explanation:** Since intervals \[1,3\] and \[2,6\] overlap, merge them into \[1,6\].

**Example 2:**

**Input:** intervals = \[\[1,4\],\[4,5\]\]
**Output:** \[\[1,5\]\]
**Explanation:** Intervals \[1,4\] and \[4,5\] are considered overlapping.

**Constraints:**

*   `1 <= intervals.length <= 104`
*   `intervals[i].length == 2`
*   `0 <= starti <= endi <= 104`
Insert Interval

You are given an array of non-overlapping intervals `intervals` where `intervals[i] = [starti, endi]` represent the start and the end of the `ith` interval and `intervals` is sorted in ascending order by `starti`. You are also given an interval `newInterval = [start, end]` that represents the start and end of another interval.

Insert `newInterval` into `intervals` such that `intervals` is still sorted in ascending order by `starti` and `intervals` still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return `intervals` _after the insertion_.

**Example 1:**

**Input:** intervals = \[\[1,3\],\[6,9\]\], newInterval = \[2,5\]
**Output:** \[\[1,5\],\[6,9\]\]

**Example 2:**

**Input:** intervals = \[\[1,2\],\[3,5\],\[6,7\],\[8,10\],\[12,16\]\], newInterval = \[4,8\]
**Output:** \[\[1,2\],\[3,10\],\[12,16\]\]
**Explanation:** Because the new interval \[4,8\] overlaps with \[3,5\],\[6,7\],\[8,10\].

**Constraints:**

*   `0 <= intervals.length <= 104`
*   `intervals[i].length == 2`
*   `0 <= starti <= endi <= 105`
*   `intervals` is sorted by `starti` in **ascending** order.
*   `newInterval.length == 2`
*   `0 <= start <= end <= 105`
Length of Last Word

Given a string `s` consisting of words and spaces, return _the length of the **last** word in the string._

A **word** is a maximal substring consisting of non-space characters only.

**Example 1:**

**Input:** s =  "Hello World "
**Output:** 5
**Explanation:** The last word is  "World " with length 5.

**Example 2:**

**Input:** s =  "   fly me   to   the moon   "
**Output:** 4
**Explanation:** The last word is  "moon " with length 4.

**Example 3:**

**Input:** s =  "luffy is still joyboy "
**Output:** 6
**Explanation:** The last word is  "joyboy " with length 6.

**Constraints:**

*   `1 <= s.length <= 104`
*   `s` consists of only English letters and spaces `' '`.
*   There will be at least one word in `s`.
Spiral Matrix II

Given a positive integer `n`, generate an `n x n` `matrix` filled with elements from `1` to `n2` in spiral order.

**Example 1:**

**Input:** n = 3
**Output:** \[\[1,2,3\],\[8,9,4\],\[7,6,5\]\]

**Example 2:**

**Input:** n = 1
**Output:** \[\[1\]\]

**Constraints:**

*   `1 <= n <= 20`
Permutation Sequence

The set `[1, 2, 3, ..., n]` contains a total of `n!` unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for `n = 3`:

1.  `"123 "`
2.  `"132 "`
3.  `"213 "`
4.  `"231 "`
5.  `"312 "`
6.  `"321 "`

Given `n` and `k`, return the `kth` permutation sequence.

**Example 1:**

**Input:** n = 3, k = 3
**Output:** "213"

**Example 2:**

**Input:** n = 4, k = 9
**Output:** "2314"

**Example 3:**

**Input:** n = 3, k = 1
**Output:** "123"

**Constraints:**

*   `1 <= n <= 9`
*   `1 <= k <= n!`
Rotate List

Given the `head` of a linked list, rotate the list to the right by `k` places.

**Example 1:**

**Input:** head = \[1,2,3,4,5\], k = 2
**Output:** \[4,5,1,2,3\]

**Example 2:**

**Input:** head = \[0,1,2\], k = 4
**Output:** \[2,0,1\]

**Constraints:**

*   The number of nodes in the list is in the range `[0, 500]`.
*   `-100 <= Node.val <= 100`
*   `0 <= k <= 2 * 109`
Unique Paths

There is a robot on an `m x n` grid. The robot is initially located at the **top-left corner** (i.e., `grid[0][0]`). The robot tries to move to the **bottom-right corner** (i.e., `grid[m - 1][n - 1]`). The robot can only move either down or right at any point in time.

Given the two integers `m` and `n`, return _the number of possible unique paths that the robot can take to reach the bottom-right corner_.

The test cases are generated so that the answer will be less than or equal to `2 * 109`.

**Example 1:**

**Input:** m = 3, n = 7
**Output:** 28

**Example 2:**

**Input:** m = 3, n = 2
**Output:** 3
**Explanation:** From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

**Constraints:**

*   `1 <= m, n <= 100`
Unique Paths II

You are given an `m x n` integer array `grid`. There is a robot initially located at the **top-left corner** (i.e., `grid[0][0]`). The robot tries to move to the **bottom-right corner** (i.e., `grid[m - 1][n - 1]`). The robot can only move either down or right at any point in time.

An obstacle and space are marked as `1` or `0` respectively in `grid`. A path that the robot takes cannot include **any** square that is an obstacle.

Return _the number of possible unique paths that the robot can take to reach the bottom-right corner_.

The testcases are generated so that the answer will be less than or equal to `2 * 109`.

**Example 1:**

**Input:** obstacleGrid = \[\[0,0,0\],\[0,1,0\],\[0,0,0\]\]
**Output:** 2
**Explanation:** There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

**Example 2:**

**Input:** obstacleGrid = \[\[0,1\],\[0,0\]\]
**Output:** 1

**Constraints:**

*   `m == obstacleGrid.length`
*   `n == obstacleGrid[i].length`
*   `1 <= m, n <= 100`
*   `obstacleGrid[i][j]` is `0` or `1`.
Minimum Path Sum

Given a `m x n` `grid` filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

**Note:** You can only move either down or right at any point in time.

**Example 1:**

**Input:** grid = \[\[1,3,1\],\[1,5,1\],\[4,2,1\]\]
**Output:** 7
**Explanation:** Because the path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum.

**Example 2:**

**Input:** grid = \[\[1,2,3\],\[4,5,6\]\]
**Output:** 12

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 200`
*   `0 <= grid[i][j] <= 100`
Valid Number

A **valid number** can be split up into these components (in order):

1.  A **decimal number** or an **integer**.
2.  (Optional) An `'e'` or `'E'`, followed by an **integer**.

A **decimal number** can be split up into these components (in order):

1.  (Optional) A sign character (either `'+'` or `'-'`).
2.  One of the following formats:
    1.  One or more digits, followed by a dot `'.'`.
    2.  One or more digits, followed by a dot `'.'`, followed by one or more digits.
    3.  A dot `'.'`, followed by one or more digits.

An **integer** can be split up into these components (in order):

1.  (Optional) A sign character (either `'+'` or `'-'`).
2.  One or more digits.

For example, all the following are valid numbers: `[ "2 ", "0089 ", "-0.1 ", "+3.14 ", "4. ", "-.9 ", "2e10 ", "-90E3 ", "3e+7 ", "+6e-1 ", "53.5e93 ", "-123.456e789 "]`, while the following are not valid numbers: `[ "abc ", "1a ", "1e ", "e3 ", "99e2.5 ", "--6 ", "-+3 ", "95a54e53 "]`.

Given a string `s`, return `true` _if_ `s` _is a **valid number**_.

**Example 1:**

**Input:** s =  "0 "
**Output:** true

**Example 2:**

**Input:** s =  "e "
**Output:** false

**Example 3:**

**Input:** s =  ". "
**Output:** false

**Constraints:**

*   `1 <= s.length <= 20`
*   `s` consists of only English letters (both uppercase and lowercase), digits (`0-9`), plus `'+'`, minus `'-'`, or dot `'.'`.
Plus One

You are given a **large integer** represented as an integer array `digits`, where each `digits[i]` is the `ith` digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading `0`'s.

Increment the large integer by one and return _the resulting array of digits_.

**Example 1:**

**Input:** digits = \[1,2,3\]
**Output:** \[1,2,4\]
**Explanation:** The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be \[1,2,4\].

**Example 2:**

**Input:** digits = \[4,3,2,1\]
**Output:** \[4,3,2,2\]
**Explanation:** The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be \[4,3,2,2\].

**Example 3:**

**Input:** digits = \[9\]
**Output:** \[1,0\]
**Explanation:** The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be \[1,0\].

**Constraints:**

*   `1 <= digits.length <= 100`
*   `0 <= digits[i] <= 9`
*   `digits` does not contain any leading `0`'s.
Add Binary

Given two binary strings `a` and `b`, return _their sum as a binary string_.

**Example 1:**

**Input:** a = "11", b = "1"
**Output:** "100"

**Example 2:**

**Input:** a = "1010", b = "1011"
**Output:** "10101"

**Constraints:**

*   `1 <= a.length, b.length <= 104`
*   `a` and `b` consist only of `'0'` or `'1'` characters.
*   Each string does not contain leading zeros except for the zero itself.
Text Justification

Given an array of strings `words` and a width `maxWidth`, format the text such that each line has exactly `maxWidth` characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces `' '` when necessary so that each line has exactly `maxWidth` characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified, and no extra space is inserted between words.

**Note:**

*   A word is defined as a character sequence consisting of non-space characters only.
*   Each word's length is guaranteed to be greater than `0` and not exceed `maxWidth`.
*   The input array `words` contains at least one word.

**Example 1:**

**Input:** words = \[ "This ",  "is ",  "an ",  "example ",  "of ",  "text ",  "justification. "\], maxWidth = 16
**Output:**
\[
    "This    is    an ",
    "example  of text ",
    "justification.   "
\]

**Example 2:**

**Input:** words = \[ "What ", "must ", "be ", "acknowledgment ", "shall ", "be "\], maxWidth = 16
**Output:**
\[
   "What   must   be ",
   "acknowledgment   ",
   "shall be         "
\]
**Explanation:** Note that the last line is  "shall be     " instead of  "shall     be ", because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified because it contains only one word.

**Example 3:**

**Input:** words = \[ "Science ", "is ", "what ", "we ", "understand ", "well ", "enough ", "to ", "explain ", "to ", "a ", "computer. ", "Art ", "is ", "everything ", "else ", "we ", "do "\], maxWidth = 20
**Output:**
\[
   "Science  is  what we ",
   "understand      well ",
   "enough to explain to ",
   "a  computer.  Art is ",
   "everything  else  we ",
   "do                   "
\]

**Constraints:**

*   `1 <= words.length <= 300`
*   `1 <= words[i].length <= 20`
*   `words[i]` consists of only English letters and symbols.
*   `1 <= maxWidth <= 100`
*   `words[i].length <= maxWidth`
Sqrt(x)

Given a non-negative integer `x`, return _the square root of_ `x` _rounded down to the nearest integer_. The returned integer should be **non-negative** as well.

You **must not use** any built-in exponent function or operator.

*   For example, do not use `pow(x, 0.5)` in c++ or `x ** 0.5` in python.

**Example 1:**

**Input:** x = 4
**Output:** 2
**Explanation:** The square root of 4 is 2, so we return 2.

**Example 2:**

**Input:** x = 8
**Output:** 2
**Explanation:** The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

**Constraints:**

*   `0 <= x <= 231 - 1`
Climbing Stairs

You are climbing a staircase. It takes `n` steps to reach the top.

Each time you can either climb `1` or `2` steps. In how many distinct ways can you climb to the top?

**Example 1:**

**Input:** n = 2
**Output:** 2
**Explanation:** There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

**Example 2:**

**Input:** n = 3
**Output:** 3
**Explanation:** There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

**Constraints:**

*   `1 <= n <= 45`
Simplify Path

Given a string `path`, which is an **absolute path** (starting with a slash `'/'`) to a file or directory in a Unix-style file system, convert it to the simplified **canonical path**.

In a Unix-style file system, a period `'.'` refers to the current directory, a double period `'..'` refers to the directory up a level, and any multiple consecutive slashes (i.e. `'//'`) are treated as a single slash `'/'`. For this problem, any other format of periods such as `'...'` are treated as file/directory names.

The **canonical path** should have the following format:

*   The path starts with a single slash `'/'`.
*   Any two directories are separated by a single slash `'/'`.
*   The path does not end with a trailing `'/'`.
*   The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period `'.'` or double period `'..'`)

Return _the simplified **canonical path**_.

**Example 1:**

**Input:** path =  "/home/ "
**Output:**  "/home "
**Explanation:** Note that there is no trailing slash after the last directory name.

**Example 2:**

**Input:** path =  "/../ "
**Output:**  "/ "
**Explanation:** Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

**Example 3:**

**Input:** path =  "/home//foo/ "
**Output:**  "/home/foo "
**Explanation:** In the canonical path, multiple consecutive slashes are replaced by a single one.

**Constraints:**

*   `1 <= path.length <= 3000`
*   `path` consists of English letters, digits, period `'.'`, slash `'/'` or `'_'`.
*   `path` is a valid absolute Unix path.
Edit Distance

Given two strings `word1` and `word2`, return _the minimum number of operations required to convert `word1` to `word2`_.

You have the following three operations permitted on a word:

*   Insert a character
*   Delete a character
*   Replace a character

**Example 1:**

**Input:** word1 =  "horse ", word2 =  "ros "
**Output:** 3
**Explanation:** 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

**Example 2:**

**Input:** word1 =  "intention ", word2 =  "execution "
**Output:** 5
**Explanation:** 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

**Constraints:**

*   `0 <= word1.length, word2.length <= 500`
*   `word1` and `word2` consist of lowercase English letters.
Set Matrix Zeroes

Given an `m x n` integer matrix `matrix`, if an element is `0`, set its entire row and column to `0`'s.

You must do it [in place](https://en.wikipedia.org/wiki/In-place_algorithm).

**Example 1:**

**Input:** matrix = \[\[1,1,1\],\[1,0,1\],\[1,1,1\]\]
**Output:** \[\[1,0,1\],\[0,0,0\],\[1,0,1\]\]

**Example 2:**

**Input:** matrix = \[\[0,1,2,0\],\[3,4,5,2\],\[1,3,1,5\]\]
**Output:** \[\[0,0,0,0\],\[0,4,5,0\],\[0,3,1,0\]\]

**Constraints:**

*   `m == matrix.length`
*   `n == matrix[0].length`
*   `1 <= m, n <= 200`
*   `-231 <= matrix[i][j] <= 231 - 1`

**Follow up:**

*   A straightforward solution using `O(mn)` space is probably a bad idea.
*   A simple improvement uses `O(m + n)` space, but still not the best solution.
*   Could you devise a constant space solution?
Search a 2D Matrix

You are given an `m x n` integer matrix `matrix` with the following two properties:

*   Each row is sorted in non-decreasing order.
*   The first integer of each row is greater than the last integer of the previous row.

Given an integer `target`, return `true` _if_ `target` _is in_ `matrix` _or_ `false` _otherwise_.

You must write a solution in `O(log(m * n))` time complexity.

**Example 1:**

**Input:** matrix = \[\[1,3,5,7\],\[10,11,16,20\],\[23,30,34,60\]\], target = 3
**Output:** true

**Example 2:**

**Input:** matrix = \[\[1,3,5,7\],\[10,11,16,20\],\[23,30,34,60\]\], target = 13
**Output:** false

**Constraints:**

*   `m == matrix.length`
*   `n == matrix[i].length`
*   `1 <= m, n <= 100`
*   `-104 <= matrix[i][j], target <= 104`
Sort Colors

Given an array `nums` with `n` objects colored red, white, or blue, sort them **[in-place](https://en.wikipedia.org/wiki/In-place_algorithm)** so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers `0`, `1`, and `2` to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

**Example 1:**

**Input:** nums = \[2,0,2,1,1,0\]
**Output:** \[0,0,1,1,2,2\]

**Example 2:**

**Input:** nums = \[2,0,1\]
**Output:** \[0,1,2\]

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 300`
*   `nums[i]` is either `0`, `1`, or `2`.

**Follow up:** Could you come up with a one-pass algorithm using only constant extra space?
Minimum Window Substring

Given two strings `s` and `t` of lengths `m` and `n` respectively, return _the **minimum window**_ **_substring_** _of_ `s` _such that every character in_ `t` _(**including duplicates**) is included in the window_. If there is no such substring, return _the empty string_ `" "`.

The testcases will be generated such that the answer is **unique**.

**Example 1:**

**Input:** s =  "ADOBECODEBANC ", t =  "ABC "
**Output:**  "BANC "
**Explanation:** The minimum window substring  "BANC " includes 'A', 'B', and 'C' from string t.

**Example 2:**

**Input:** s =  "a ", t =  "a "
**Output:**  "a "
**Explanation:** The entire string s is the minimum window.

**Example 3:**

**Input:** s =  "a ", t =  "aa "
**Output:**  " "
**Explanation:** Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

**Constraints:**

*   `m == s.length`
*   `n == t.length`
*   `1 <= m, n <= 105`
*   `s` and `t` consist of uppercase and lowercase English letters.

**Follow up:** Could you find an algorithm that runs in `O(m + n)` time?
Combinations

Given two integers `n` and `k`, return _all possible combinations of_ `k` _numbers chosen from the range_ `[1, n]`.

You may return the answer in **any order**.

**Example 1:**

**Input:** n = 4, k = 2
**Output:** \[\[1,2\],\[1,3\],\[1,4\],\[2,3\],\[2,4\],\[3,4\]\]
**Explanation:** There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., \[1,2\] and \[2,1\] are considered to be the same combination.

**Example 2:**

**Input:** n = 1, k = 1
**Output:** \[\[1\]\]
**Explanation:** There is 1 choose 1 = 1 total combination.

**Constraints:**

*   `1 <= n <= 20`
*   `1 <= k <= n`
Subsets

Given an integer array `nums` of **unique** elements, return _all possible_ _subsets_ _(the power set)_.

The solution set **must not** contain duplicate subsets. Return the solution in **any order**.

**Example 1:**

**Input:** nums = \[1,2,3\]
**Output:** \[\[\],\[1\],\[2\],\[1,2\],\[3\],\[1,3\],\[2,3\],\[1,2,3\]\]

**Example 2:**

**Input:** nums = \[0\]
**Output:** \[\[\],\[0\]\]

**Constraints:**

*   `1 <= nums.length <= 10`
*   `-10 <= nums[i] <= 10`
*   All the numbers of `nums` are **unique**.
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:**

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

**Example 2:**

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

**Example 3:**

**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`?