# Posts tagged as “DFS”

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.

Idea:

DFS

Solution:

``````/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
for (let x = 0; x < board[0].length; x++)
for (let y = 0; y < board.length; y++)
if (dfs(board, word, 0, x, y)) return true;
return false;
};

function dfs(board, word, i, x, y) {
// exit recursion:
if (x < 0 || y < 0 || x >= board[0].length || y >= board.length || word[i] !== board[y][x])
return false;
// found the last letter
if (i === word.length - 1)
return true;

let cur = board[y][x];
// mark it 0 means already visit
board[y][x] = 0;
let found = dfs(board, word, i + 1, x + 1, y) ||
dfs(board, word, i + 1, x - 1, y) ||
dfs(board, word, i + 1, x, y + 1) ||
dfs(board, word, i + 1, x, y - 1);
// recover
board[y][x] = cur;
return found;
}``````

There are `N` rooms and you start in room `0`.  Each room has a distinct number in `0, 1, 2, ..., N-1`, and each room may have some keys to access the next room.

Formally, each room `i` has a list of keys `rooms[i]`, and each key `rooms[i][j]` is an integer in `[0, 1, ..., N-1]` where `N = rooms.length`.  A key `rooms[i][j] = v` opens the room with number `v`.

Initially, all the rooms start locked (except for room `0`).

You can walk back and forth between rooms freely.

Return `true` if and only if you can enter every room.

Example 1:

```Input: [[1],[2],[3],[]]
Output: true
Explanation:
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.
```

Example 2:

```Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.
```

Note:

1. `1 <= rooms.length <= 1000`
2. `0 <= rooms[i].length <= 1000`
3. The number of keys in all rooms combined is at most `3000`.

Idea:

DFS

Solution:

``````/**
* @param {number[][]} rooms
* @return {boolean}
*/
var canVisitAllRooms = function(rooms) {
let visited = [];
dfs(rooms, visited, 0);
return visited.length === rooms.length;
};

function dfs(rooms, visited, roomNum){
// exit recursion:
if (visited.includes(roomNum)) return;

visited.push(roomNum);
// possible solution
for (let key of rooms[roomNum])
dfs(rooms, visited, key);
}``````

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

Solution 1: (DFS)

``````/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
return dfs(matrix, target, 0, 0);
};

function dfs(matrix, target, x, y) {
let rows = matrix.length;
let cols = matrix[0].length;

// exit recursion condition, reach to the end;
if (y === rows) return false;

// traverse from left to right, then next row
let nextX = (x + 1) % cols;
let nextY = nextX === 0 ? y + 1 : y;

if (matrix[y][x] === target)
return true;
else
return dfs(matrix, target, nextX, nextY);

return false;
}``````

Solution 2: (Binary Search) Better and Faster!

• Time complexity: O(log(mn))
• Space complexity: O(1)
``````var searchMatrix = function(matrix, target) {
let cols = matrix[0].length;
// 	treat 2D as 1D, use binary search
let l = 0;
let r = matrix.length * cols;
while (l < r) {
let mid = l + Math.floor((r - l) / 2);
let row = Math.floor(mid / cols);
let col = mid % cols;
if (matrix[row][col] === target) {
return true;
} else if (matrix[row][col] > target) {
r = mid;
} else {
l = mid + 1;
}
}
return false;
};``````

Given an `m x n` 2D binary grid `grid` which represents a map of `'1'`s (land) and `'0'`s (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

```Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
```

Example 2:

```Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
```

Constraints:

• `m == grid.length`
• `n == grid[i].length`
• `1 <= m, n <= 300`
• `grid[i][j]` is `'0'` or `'1'`.

Idea:

Traverse connected components: Use DFS to traverse 4 directions and mark them “0” if found “1”

Solution:

``````/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
let row = grid.length;
if (row === 0) return 0;
let col = grid[0].length;
let res = 0;
for (let x = 0; x < col ; x++) {
for (let y = 0; y < row; y++) {
if (grid[y][x] === "1") {
res++;
dfs(grid, x, y, col, row);
}
}
}
return res;
};

var dfs = function(grid, x, y, n, m) {
// over boundry cases and not "1" => return
if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] === "0") return;

// already visited mark it "0"
grid[y][x] = "0";
// traverse 4 directions if any "1" => mark them "0"
dfs(grid, x + 1, y, n, m);
dfs(grid, x - 1, y, n, m);
dfs(grid, x, y + 1, n, m);
dfs(grid, x, y - 1, n, m);
}``````

Given a string containing digits from `2-9` inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

```Input: digits = "23"
```

Example 2:

```Input: digits = ""
Output: []
```

Example 3:

```Input: digits = "2"
Output: ["a","b","c"]
```

Constraints:

• `0 <= digits.length <= 4`
• `digits[i]` is a digit in the range `['2', '9']`.

Idea:

Use DFS template

Solution:

``````/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
let res = [];
if (digits.length === 0) return res;
// you can use array or use hashmap
const nums = [];
nums[2] = ['a','b','c'];
nums[3] = ['d','e','f'];
nums[4] = ['g','h','i'];
nums[5] = ['j','k','l'];
nums[6] = ['m','n','o'];
nums[7] = ['p','q','r','s'];
nums[8] = ['t','u','v'];
nums[9] = ['w','x','y','z'];
dfs(res, 0, "", nums, digits);
return res;
};

function dfs(res, start, cur, nums, digits) {
// exit recursive conditon
if (cur.length === digits.length) {
res.push(cur);
return;
}
// possible solution
let possibleLetters = nums[digits[start]];
for (let letter of possibleLetters) {
// modify: add the letter to our current solution
cur += letter;
dfs(res, start + 1, cur, nums, digits);
// recover: backtrack by removing the letter
// before moving onto the next
cur = cur.substring(0, cur.length - 1);
}
}``````

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

Example 1:

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

Example 2:

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

Example 3:

```Input: nums = [1]
Output: [[1]]
```

Constraints:

• `1 <= nums.length <= 6`
• `-10 <= nums[i] <= 10`
• All the integers of `nums` are unique.

Idea:

Use DFS template

Solution:

``````/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
let res = [];
let cur = [];
let len = nums.length;
let used = new Array(len).fill(false);
dfs(nums, len, res, cur, used);
return res;
}

function dfs(nums, len, res, cur, used) {
// exit recursive condition
if (cur.length === len) {
res.push(cur.concat());
return;
}

// possible solution
for (let i = 0; i < len; i++) {
// skip used integer
if (used[i]) continue;

// modify current state
used[i] = true;
cur.push(nums[i]);
dfs(nums, len, res, cur, used);
// recover current state
cur.pop();
used[i] = false;
}
}``````

Given a collection of candidate numbers (`candidates`) and a target number (`target`), find all unique combinations in `candidates` where the candidate numbers sum to `target`.

Each number in `candidates` may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

```Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
```

Example 2:

```Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]
```

Constraints:

• `1 <= candidates.length <= 100`
• `1 <= candidates[i] <= 50`
• `1 <= target <= 30`

Idea:

DFS

• Important Step: sort the array
• Create a DFS recursive and keep tracking target value and start index
• Exit DFS recursive:
• if (target < 0) return;
• if (target === 0) record answer and return;
• For loop (Possible solution) pay attention to:
• No duplication
• Candidates can only be used once

Solution:

``````/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/

var combinationSum2 = function(candidates, target) {
let res = [];
let cur = [];
// Important Step: sort the array
candidates.sort();
dfs(res, cur, 0, candidates, target);
return res;
}

function dfs(res, cur, start, can, target) {
// exit recursive condition
if (target < 0) return;
if (target === 0) {
res.push(cur.concat());
return;
}

for (let i = start; i < can.length; i++) {
// skip duplicate
if (i > start && can[i] === can[i - 1]) continue;
cur.push(can[i]);
// Each number in candidates may only be used once
// in the combination. start from i + 1
dfs(res, cur, i + 1, can, target - can[i]);
cur.pop();
}

}``````

Given an input string (`s`) and a pattern (`p`), implement regular expression matching with support for `'.'` and `'*'` where:

• `'.'` Matches any single character.​​​​
• `'*'` Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Example 1:

```Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
```

Example 2:

```Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
```

Example 3:

```Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
```

Example 4:

```Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
```

Example 5:

```Input: s = "mississippi", p = "mis*is*p*."
Output: false
```

Constraints:

• `0 <= s.length <= 20`
• `0 <= p.length <= 30`
• `s` contains only lowercase English letters.
• `p` contains only lowercase English letters, `'.'`, and `'*'`.
• It is guaranteed for each appearance of the character `'*'`, there will be a previous valid character to match.

Idea:

Backtracking / Depth-first search (DFS)

There are two normal cases without consideration of `*`:

`1. s === p2. s !== p, but p === '.' and s is any character`

And then let’s consider how to handle the pattern `*`:

If we have a `x*` in the pattern(x stands for any character), we may ignore this part of
the pattern, or delete a matching character in the text

```// no match: aa , c*                || match: aaa , a*
(isMatch(s, p.substring(2)) || (first_match && isMatch(s.substring(1), p)));```

According to these analyses, we can construct a depth-first search algorithm, it’s a recursive algorithm.

Solution:

``````/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
let sLen = s.length;
let pLen = p.length;
if (pLen === 0) return sLen === 0;
let first_match = (sLen !== 0 && (p[0] === s[0] || p[0] === '.'));

// If a star is present in the pattern, it will be in the
// second position p[1]. Then, we may ignore this part of
// the pattern, or delete a matching character in the text.
// If we have a match on the remaining strings after any of
// these operations, then the initial inputs matched.
if (pLen >= 2 && p[1] === '*') {
// no match:  aa , c*       ||      match:       aaa , a*
return (isMatch(s, p.substring(2)) || (first_match && isMatch(s.substring(1), p)));
} else {
return first_match && isMatch(s.substring(1), p.substring(1));
}
};
``````

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.

Idea:

DFS(Depth First Search)

DFS Template:

``````function dfs(nums, n, start, cur, res...) {
if (exit recursive condition) {
return;
}
for (possible solution) {
// modify current state
dfs(nums, n, i + 1, cur, res...);
// recover current state

}
return something if need // option
};``````

Solution:

``````/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
let cur = [];
let res = [];
for (let i = 0; i <= nums.length; i++) {
dfs(nums, i, 0, cur, res);
}
return res;
};

var dfs = function(nums, n, start, cur, res) {
// exit recursive condition
if (cur.length === n) {
res.push(cur.concat());
return;
}

// possible solution
for (let i = start; i < nums.length; i++) {
// modify current state
cur.push(nums[i]);
dfs(nums, n, i + 1, cur, res);
// recover current state
cur.pop();
}
};``````