Categories

## 90. Subsets II Leetcode Javascript Solution

The Problem:

Given an integer array `nums` that may contain duplicates, 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,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
```

Example 2:

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

Constraints:

• `1 <= nums.length <= 10`
• `-10 <= nums[i] <= 10`

The Solution:

```var subsetsWithDup = function(nums) {
let results = [],temp = []
nums.sort((a,b) => a-b)
console.log(nums)
function backtrack(nums,start,results, temp){
results.push([...temp])
/* console.log("results " )
for( rest of results){
console.log(rest)
}
*/
for(let i = start; i < nums.length; i++){
//console.log("i " + i)
if(i == start || nums[i] != nums[i-1]){
//                 console.log("i after if" + i)
temp.push(nums[i])
//   console.log(temp)
backtrack(nums,i+1,results,temp)
temp.pop()
//                console.log("temp after pop " + temp)
}
}
}
backtrack(nums,0,results,temp)
return results
};```
Categories

## 980. Unique Paths III Leetcode Javascript Solution

The Problem:

On a 2-dimensional `grid`, there are 4 types of squares:

• `1` represents the starting square.  There is exactly one starting square.
• `2` represents the ending square.  There is exactly one ending square.
• `0` represents empty squares we can walk over.
• `-1` represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Example 1:

```Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)```

Example 2:

```Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)```

Example 3:

```Input: [[0,1],[2,0]]
Output: 0
Explanation:
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.
```

Note:

1. `1 <= grid.length * grid[0].length <= 20`

The Solution

We’ll need to rely on backtracking and DFS to solve this problem

```var uniquePathsIII = function(grid) {
let empties = 0, res = 0, start, end
for(let i = 0; i < grid.length; i ++){
for(let j = 0; j < grid[0].length; j++){
if(grid[i][j] == 0){
empties++
} else if (grid[i][j] == 1){
start = i
end = j
}
}
}
function  dfs(i,j,grid,count){
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == -1 ){
return
}
if(grid[i][j] == 1 && count > 0){
return
}
if(grid[i][j] == 2){
//  console.log(count)
if( empties == count){
res++
}
return
}
if(grid[i][j] == 0){
count++
// let step = grid[i][j]
grid[i][j] = -1
}
dfs(i-1,j,grid,count)
dfs(i,j-1,grid,count)
dfs(i+1,j,grid,count)
dfs(i,j+1,grid,count)
if(grid[i][j] == -1){
count--
grid[i][j] = 0
}
}
dfs(start,end,grid,0)
return res
};```
Categories

## 212. Word Search II Leetcode Javascript Solution

The Problem:

Given an `m x n` `board` of characters and a list of strings `words`, return all words on the board.

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

Example 1:

```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"]
```

Example 2:

```Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
```

Constraints:

• `m == board.length`
• `n == board[i].length`
• `1 <= m, n <= 12`
• `board[i][j]` is a lowercase English letter.
• `1 <= words.length <= 3 * 104`
• `1 <= words[i].length <= 10`
• `words[i]` consists of lowercase English letters.
• All the strings of `words` are unique.

The Solution:

We will use the Trie data structure to store all the words for faster and easier lookup. Then to search for all the words on the board, we’ll use depth-first search and backtracking.

```var findWords = function(board, words) {
let res = []
function buildTrie(words){
let root = {}
for(let word of words){
let node = root
for (let c of word.split('')){
if(!node[c]) node[c] = {}
node = node[c]
}
node.word = word
}
return root
}
let root = buildTrie(words)
//console.log(JSON.stringify(root))
function dfs(board,i,j,root,res){
if(root.word){
console.log(root.word)
res.push(root.word)
root.word = null
}
if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || !root[board[i][j]]){
return false
}
let c = board[i][j]
board[i][j] = ""
let result = dfs(board,i-1, j, root[c],res) || dfs(board,i, j-1, root[c],res) || dfs(board,i+1, j, root[c],res) || dfs(board,i, j+1, root[c],res)
board[i][j] = c
return result
}
for(let i = 0 ; i < board.length; i++){
for(let j = 0 ; j < board[0].length; j++){
dfs(board,i, j, root,res)
}
}
return res
};```