Generate Parentheses (Java)

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"




Solution: Greedy and Recursive

Take advantage of the feature of parentheses, left side and right side must match each other,  in other words, if there a left side parenthese,  whatever position it is, there must be a right side parenthese to match it.

Permutations (Java)

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Path Sum (Java and Python)

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Combinations (Java)

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution: a classical DFS problem, pay attention to the format of solve this question which can be apply to many other DFS problems

Minimum Depth of Binary Tree (Python and Java)

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Search in Rotated Sorted Array (Java+Python)

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

       

Search a item in sorted array we should think about binary search. Cause the given array has been rotated unknow times, so binary search can not be apply directly here.

       

Throgh observation we can see, no matter how a sorted array be rotated, there is

 always one side is sorted.

       

So we can pick the middle item at first and compare it with given array's leftMost and rightMost items to check which side is sorted, for given example 4, 5 , 6, 7 , 0 , 1, 2

mid is 7, leftMost is 4, rightMost is 2, because of 4<7 so we can know left side is sorted.

       

Depend on the conclusion we got above, if the given target is between 4->7, such as 6, we can just seach left side for it, otherwise we search the right side.

       

A trick situation is when duplicate exist in the array, discard the requriement of this quesiton, my         solution will also cover duplicate exist situation. 

If duplicate exist, then leftMost or rightMost item may equal to middle item, if only one of them equal to mid such as A[leftMost]==A[mid] then from leftMost to Mid should have same value. then we can only search the right side from mid to right most. If both A[rightMost] and A[leftMost] equal to A[Mid] we have to search both sides.

Path Sum II (Java)

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Solution:  DFS

Apply DFS check every possible combination, record result if meet requirement

Flatten Binary Tree to Linked List (Java)

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Solution:

Divide and Conquer, convert left and right tree to list separately, then connect root. right to list converted by left tree, make root. left to null, then search for the lastNode of right tree and connect it to list converted by original right tree.

Pow(x, n) (Java)

LeetCode:

Implement pow(x, n).

Solution: Binary Search

N-Queens (Java)

Leetcode

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Slution: DFS

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

Construct Binary Tree from Inorder and Postorder Traversal (Java)

LeetCode

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Construct Binary Tree from Preorder and Inorder Traversal (Java)

LeetCode

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution: Divide and Conquer

According to the rule of preorder traversal,  the first item in the preorder array must be the root. and the question also told us "You may assume that duplicates do not exist in the tree." so we can go through inorder array find the root's position, then  we got left tree and right tree. finally we can apply recursion to got the tree we want base on above logic.

Palindrome Partitioning (Java)

LeetCode

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Solution: DFS, Recursion

declare start point st, make it move from 0-> s.length(), for each st, check every substring generated by st and i, st+1<=i<=s.length(), if the substring is a palindrome then put it into ArrayList<String>  partition, if st reach s.length() mean we got a valid partition for given string s, then put it into ArrayList<ArrayList<String>> result;

Combination Sum II (Java)

LeetCode

Given a collection of candidate numbers (C) and a target number (T), 

find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8, 
A solution set is: 
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6] 

Solution: DFS

     Apply DFS continually check every combination, if any one meet the target put it into result arraylist.

Scramble String (Java)

Scramble String

 Total Accepted: 3103 Total Submissions: 15043

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Sudoku Solver (Java)

LeetCode

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

Solution: declare a function called isValid used to check if num from 1->9 will not conflict with nums which were already existed in the board, if it isValid, then recursively  call solved function to check if the board can be finally filled.

Clone Graph (Java)

LeetCode

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution: DFS traverse all nodes, meanwhile use HashMap to record the node which has been cloned. use label as key and the new created node as value

Restore IP Addresses (Java)

LeetCode

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

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Solution:

DFS to combine each possible result, meanwhile skip all impossible combination for result, such as

rest letters in s can not be more than 3* rest parts and rest letters can not be less than rest parts.

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.