Posts published in “Search”

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],
]

Solution: DFS

Time complexity: O(C(n, k))
Space complexity: O(k)

Related Problems

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Solution: DFS

The range of valid numbers is [0, 255]

Time complexity: O(3^4)
Space complexity: O(1)

C++

In an n*n grid, there is a snake that spans 2 cells and starts moving from the top left corner at (0, 0) and (0, 1). The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at (n-1, n-2) and (n-1, n-1).

In one move the snake can:

• Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
• Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
• Rotate clockwise if it’s in a horizontal position and the two cells under it are both empty. In that case the snake moves from (r, c) and (r, c+1) to (r, c) and (r+1, c).
• Rotate counterclockwise if it’s in a vertical position and the two cells to its right are both empty. In that case the snake moves from (r, c) and (r+1, c) to (r, c) and (r, c+1).

Return the minimum number of moves to reach the target.

If there is no way to reach the target, return -1.

Example 1:

Input: grid = [[0,0,0,0,0,1],
[1,1,0,0,1,0],
[0,0,0,0,1,1],
[0,0,1,0,1,0],
[0,1,1,0,0,0],
[0,1,1,0,0,0]]
Output: 11
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].

Example 2:

Input: grid = [[0,0,1,1,1,1],
[0,0,0,0,1,1],
[1,1,0,0,0,1],
[1,1,1,0,0,1],
[1,1,1,0,0,1],
[1,1,1,0,0,0]]
Output: 9

Constraints:

• 2 <= n <= 100
• 0 <= grid[i][j] <= 1
• It is guaranteed that the snake starts at empty cells.

Solution1: BFS

Time complexity: O(n^2)
Space complexity: O(n^2)

Solution 2: DP

dp[i][j].first = min steps to reach i,j (tail pos) facing right
dp[i][j].second = min steps to reach i, j (tail pos) facing down
ans = dp[n][n-1].first

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must 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 in a word.

Example:

Input:
board = [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Note:

1. All inputs are consist of lowercase letters a-z.
2. The values of words are distinct.

Solution 1: DFS

Time complexity: O(sum(m*n*4^l))
Space complexity: O(l)

Solution 2: Trie

Store all the words into a trie, search the board using DFS, paths must be in the trie otherwise there is no need to explore.

Time complexity: O(sum(l) + 4^max(l))
space complexity: O(sum(l) + l)

C++

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Solution: DFS

The key to this problem is how to remove/avoid duplicates efficiently.

For the same depth, among the same numbers, only the first number can be used.

Time complexity: O(2^n * n)
Space complexity: O(n)

C++

Mission News Theme by Compete Themes.