# LeetCode 79. Word Search

## Description

Word Search

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:

``````board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
``````

`board`中查找是否存在相连（相邻）的字符与给定的单词对应。

# LeetCode 78. Subsets

## Description

Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

# LeetCode 77. Combinations

## Description

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

``````Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
``````

# LeetCode 76. Minimum Window Substring

## Description

Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

``````Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
``````

Note:

• If there is no such window in S that covers all characters in T, return the empty string “".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

# LeetCode 75. Sort Colors

## Description

Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

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

Note: You are not suppose to use the library's sort function for this problem.

Example:

``````Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
``````
• A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

• Could you come up with a one-pass algorithm using only constant space?

# LeetCode 74. Search a 2D Matrix

## Description

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

``````Input:
matrix = [
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]

target = 3
Output: true

target = 13
Output: false
``````

# LeetCode 73. Set Matrix Zeroes

## Description

Set Matrix Zeroes

Given a m x n matrix, if an element is `0`, set its entire row and column to 0. Do it in-place. Example 1:

``````Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
``````

Example 2:

``````Input:
[
[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]
]
``````

• A straight forward 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?

`m x n`的矩阵中，如果一个元素为`0`，则将它所在的行和列都置为`0`

# LeetCode 72. Edit Distance

## Description

Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. 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')
``````

Programer

ChengDu·China