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

```
def exist(self, board, word):
if not board:
return False
for i in xrange(len(board)):
for j in xrange(len(board[0])):
if self.dfs(board, i, j, word):
return True
return False
# check whether can find word, start at (i,j) position
def dfs(self, board, i, j, word):
if len(word) == 0: # all the characters are checked
return True
if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or word[0]!=board[i][j]:
return False
tmp = board[i][j] # first character is found, check the remaining part
board[i][j] = "#" # avoid visit agian
# check whether can find "word" along one direction
res = self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) \
or self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:])
board[i][j] = tmp
return res
```

## Related Problems

Given an array of **distinct** integers candidates and a target integer target, return *a list of all ***unique combinations*** of *candidates* where the chosen numbers sum to *target*.* You may return the combinations in **any order**.

The **same** number may be chosen from candidates an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you **must** take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are **sorted lexicographically** by the rules of this new language.

Return *a string of the unique letters in the new alien language sorted in ***lexicographically increasing order*** by the new language's rules. *If there is no solution, return ""*. *If there are multiple solutions, return* ***any of them**.

Given an array nums of distinct integers, return *all the possible permutations*. You can return the answer in **any order**.