Categories
Uncategorized

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
Uncategorized

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
Uncategorized

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
};