Valid Sudoku (Java)

LeetCode

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Solution: Helpe table

Declare 9 boolean array with length 9  separately for rows, columns and blocks and hold them in ArrayList. Because the number range of sudoku is 1-9, so each number in each row, col and block should be unique, then we can go through every position of given board, check if the number has been

Found in current row,current column  and current block. If so, return false;

*** Be careful about the index of block in blockChecker

Triangle (Java)

LeetCode

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Solution: DP (met during Amazon interview)

Declare pathSum array with length of triangle size(). For triangle, the bottom row length is equal to the height of triangle, so use pathSum to hold the bottom row's value, then from bottom to up, find minimum path

Letter Combinations of a Phone Number (Java)

Leetcode

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Solution: DFS, Helper table

Longest Substring Without Repeating Characters (Java)

Leetcode

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Maximal Rectangle (Java)

LeetCode

Maximal Rectangle

 Total Accepted: 2599 Total Submissions: 12591

Given a 2D binary matrix filled with 0's and 1's,

 find the largest rectangle containing all ones and 

return its area.

Similar question with largest rectangle in histogram but 

more tough.

we can apply a helper table to convert matrix to another

int[][] helper with calculate the current height for 1 at each 

column until current row.

Such as

char[][] matrix       -> int[][] helper

0,0,0,1,0                   0,0,0,1,0

0,1,1,0,1                   0,1,1,0,1

0,1,1,1,0                   0,2,2,1,0

0,0,1,0,1                   0,0,3, 0,1

then we can apply the method used in largest rectangle in

histogram to get max area which used current row as bottom

then keep updating max area.

LeetCode Word Search (Java)

LeetCode Word Search  (Java)

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.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Solution:

Applied Helper table and DFS to solve it, for each char in board, check if it is matched in word, if so, recursively check the rest chars in word.