# Wildcard Matching

Implement wildcard pattern matching with support for `'?'` and `'*'`.

• `'?'` Matches any single character.
• `'*'` Matches any sequence of characters (including the empty sequence).

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

Example
```<code>isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false</code>```

Solution1. Dynamic Programming

isMatch[i][j] = if first i chars for s can match first j chars of p

j==’*’: OR(isMatch[0~i][j-1])

j==’?’: isMatch[i-1][j-1]

else: isMatch[i-1][j-1] && s.charAt(i-1)==p.charAt(j-1)

```public boolean isMatch(String s, String p) {
//dp version
if (s == null || p == null) {
return false;
}
boolean[][] isMatch = new boolean[s.length() + 1][p.length() + 1];
isMatch = true;
for (int i = 1; i <= s.length(); i++) {
isMatch[i] = false;
}
for (int j = 1; j <= p.length(); j++) {
isMatch[j] = isMatch[j - 1] && p.charAt(j - 1) == '*';
}
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) == '*') {
for (int k = 0; k <= i; k++) {
if (isMatch[k][j - 1]) {
isMatch[i][j] = true;
break;
}
}
} else if (p.charAt(j - 1) == '?') {
isMatch[i][j] = isMatch[i - 1][j - 1];
} else {
isMatch[i][j] = isMatch[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1);
}
}
}
return isMatch[s.length()][p.length()];
}```

# Longest Common Subsequence

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Example

For `"ABCD"` and `"EDCA"`, the LCS is `"A"` (or `"D"`, `"C"`), return `1`.

For `"ABCD"` and `"EACB"`, the LCS is `"AC"`, return `2`.

Clarification

What’s the definition of Longest Common Subsequence?

Solution: Dynamic Programming

```public int longestCommonSubsequence(String A, String B) {
if (A == null || A.length() == 0 || B == null || B.length() == 0) {
return 0;
}
int[][] lcs = new int[A.length()][B.length()];
for (int i = 0; i < A.length(); i++) {
for (int j = 0; j < B.length(); j++) {
if (i == 0 || j == 0) {
lcs[i][j] = A.charAt(i) == B.charAt(j) ? 1 : 0;
} else {
if (A.charAt(i) == B.charAt(j)) {
lcs[i][j] = lcs[i - 1][j - 1] + 1;
} else {
lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
}
}
}
}
return lcs[A.length() - 1][B.length() - 1];
}```

# Longest Common Substring

Given two strings, find the longest common substring.

Return the length of it.

Example
Given A = “ABCD”, B = “CBCE”, return 2.

Note
The characters in substring should occur continuously in original string. This is different with subsequence.

Challenge
O(n x m) time and memory.

Solution: Dynamic Programming

```public int longestCommonSubstring(String A, String B) {
int[][] lcs = new int[A.length()][B.length()];
int max = 0;
for (int i = 0; i < A.length(); i++) {
for (int j = 0; j < B.length(); j++) {
if (A.charAt(i) == B.charAt(j)) {
if (i == 0 || j == 0) {
lcs[i][j] = 1;
} else {
lcs[i][j] = lcs[i - 1][j - 1] + 1;
}
}
if (lcs[i][j] > max) {
max = lcs[i][j];
}
}
}
return max;
}```

# Word Break

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Example

Given s = `"lintcode"`, dict = `["lint", "code"]`.

Return true because “lintcode” can be break as `"lint code"`.

## Version 1. DP 常规做法 无优化 straight forward

```    public boolean wordSegmentation(String s, Set < String > dict) {
if (s == null || dict == null) {
return false;
}
//result[i] means if s.subString(0,i+1) can be break.
boolean[] result = new boolean[s.length() + 1];
result = true;
for (int i = 0; i < s.length(); i++) {
if (dict.contains(s.substring(0, i + 1))) {
result[i + 1] = true;
} else {
for (int j = 0; j < i; j++) {
if (result[j + 1] && dict.contains(s.substring(j + 1, i + 1))) {
result[i + 1] = true;
break;
}
}
}
}
return result[s.length()];
}```

# Jump Game

## 1. Jump Game（问能不能跳到）

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example

A = `[2,3,1,1,4]`, return `true`.

A = `[3,2,1,0,4]`, return `false`.

Solution: Dynamic Programming.

f[i] = if it is possible to jump to i from the beginning.

f[i] = OR(f[j], j < i && j能够跳到i)

```  public boolean canJump(int[] A) {
if(A==null|| A.length==0){
return false;
}
boolean[] resultMap = new boolean[A.length];
resultMap = true;
for(int i=1;i<A.length;i++){
for(int j=0;j<i;j++){
if(resultMap[j] && (i-j)<=A[j]){
resultMap[i] = true;
break;
}
}
}
return resultMap[A.length-1];
}```

## 2. Jump Game II（问最小step数）

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

### Version 1. DP做法 不是最优 这道题可以用greedy

```  public int jump(int[] A) {
if(A==null||A.length==0){
return 0;
}
//minimum number of jumps from start to i
int[] resultMap = new int[A.length];
resultMap = 0;
for(int i=1;i<A.length;i++){
resultMap[i] = -1;
for(int j=0;j<i;j++){
if(resultMap[j]>=0 && (i-j)<=A[j]){
resultMap[i] = resultMap[j]+1;
break; //这里包含Greedy思想，最先出现的一定是最优的
}
}
}
return resultMap[A.length-1];
}```

### Version 2. Greedy (O(n) One pass)

```public int jump(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int start = 0, end = 0, jump = 0;
while (end < A.length) {
jump++;
int furthest = end;
for (int i = start; i <= end; i++) {
if (A[i] + i > furthest) {
furthest = A[i] + i;
}
}
start = end + 1;
end = furthest;
if (start > end) {
return -1; //if can not jump to the end
}
}
return jump;
}```

# Triangle

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

Example

For example, given the following triangle
[
,
[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.

Version 1. Up-Bottom

`//f[i][j] = Math.min(f[i-1][j-1], f[i-1][j])+grid[i][j]`
```public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
//O(n^2) space
//f[i][j] = Math.min(f[i-1][j-1], f[i-1][j])+grid[i][j]
if (triangle == null || triangle.size() == 0) {
return 0;
}
int size = triangle.size();
int[][] resultMap = new int[size][size];
resultMap = triangle.get(0).get(0);
for (int i = 1; i < size; i++) {
ArrayList<Integer> curr = triangle.get(i);
for (int j = 0; j < curr.size(); j++) {
if (j == 0) {
resultMap[i][j] = resultMap[i - 1][j] + curr.get(j);
} else {
if (j < triangle.get(i - 1).size()) {
resultMap[i][j] = Math.min(resultMap[i - 1][j - 1], resultMap[i - 1][j]) + curr.get(j);
} else {
resultMap[i][j] = resultMap[i - 1][j - 1] + curr.get(j);
}
}
}
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < size; i++) {
if (resultMap[size - 1][i] < min) {
min = resultMap[size - 1][i];
}
}
return min;
}```

Version 2. Bottom-Up O(n^2) space

```    public int minimumTotal(ArrayList < ArrayList < Integer >> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}
int size = triangle.size();
int[][] resultMap = new int[size][size];
//init the last row
ArrayList < Integer > lastRow = triangle.get(size - 1);
for (int i = 0; i < size; i++) {
resultMap[size - 1][i] = lastRow.get(i);
}
//from bottom to top
for (int i = size - 2; i >= 0; i--) {
ArrayList < Integer > curr = triangle.get(i);
for (int j = 0; j < curr.size(); j++) {
resultMap[i][j] = Math.min(resultMap[i + 1][j], resultMap[i + 1][j + 1]) + curr.get(j);
}
}
return resultMap;
}```

Version 3. Bottom-Up O(n) space

```    public int minimumTotal(ArrayList < ArrayList < Integer >> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}
int size = triangle.size();
int[][] resultMap = new int[size];
//init the last row
ArrayList < Integer > lastRow = triangle.get(size - 1);
for (int i = 0; i < size; i++) {
resultMap[(size - 1) % 2][i] = lastRow.get(i);
}
//from bottom to top
for (int i = size - 2; i >= 0; i--) {
ArrayList < Integer > curr = triangle.get(i);
for (int j = 0; j < curr.size(); j++) {
resultMap[i % 2][j] = Math.min(resultMap[(i + 1) % 2][j], resultMap[(i + 1) % 2][j + 1]) + curr.get(j);
}
}
return resultMap;
}```

# Leetcode: Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

1. Recursive Solution

``` public int minPathSum(int[][] grid) {
if (grid.length == 0 || grid.length == 0) {
return 0;
}
int[][] resultMap = new int[grid.length][grid.length];
return minPathSum(grid, resultMap, grid.length-1, grid.length-1);
}

public int minPathSum(int[][] grid, int[][] resultMap, int row, int col) {
if (row < 0 || col < 0) {
return Integer.MAX_VALUE;
}
if (row == 0 && col == 0) {
return grid;
}
if (resultMap[row][col] == 0) {
resultMap[row][col] = grid[row][col] + Math.min(minPathSum(grid, resultMap, row - 1, col), minPathSum(grid, resultMap, row, col - 1));
}
return resultMap[row][col];
}```

Note:

This is a very typical dp problem. where dp[i][j] = grid[i][j] + min( dp[i-1][j], dp[i][j-1] ); To prevent same cell being visited and calculated multiple times, we have a resultMap 2d array to store the result. We also need to check the edge carefully to ensure the index is not out of bounds of the given array.

2. Iterative Solution (O(m*n) space)

```public class Solution {
public int minPathSum(int[][] grid) {
if(grid.length==0||grid.length==0){
return 0;
}
//2D map -- O(m*n) space
int[][] resultMap = new int[grid.length][grid.length];
resultMap = grid;
//Calculate the first row
for(int i = 1;i<grid.length;i++){
resultMap[i] = grid[i] + resultMap[i-1];
}
//Calculate the first col
for(int i = 1;i<grid.length;i++){
resultMap[i] = grid[i] + resultMap[i-1];
}
//Calculate the rest
for(int i=1;i<grid.length;i++){
for(int j=1;j<grid.length;j++){
resultMap[i][j] = grid[i][j]+Math.min(resultMap[i-1][j],resultMap[i][j-1]);
}
}
return resultMap[grid.length-1][grid.length-1];
}
}```

Note: First calculate first row and first col which is there own grid value, then calculate other cells based on it.

3. *Optimal* Iterative Solution (O(n) space)

```public class Solution {
public int minPathSum(int[][] grid) {
if (grid.length == 0 || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid.length;

//1D map -- O(n) space, n is # of cols
int[] resultMap = new int[cols];
resultMap = grid;

//Calculate the first row
for (int i = 1; i < grid.length; i++) {
resultMap[i] = grid[i] + resultMap[i - 1];
}

for (int i = 1; i < rows; i++) {
resultMap = resultMap + grid[i];
for (int j = 1; j < cols; j++) {
resultMap[j] = grid[i][j] + Math.min(resultMap[j], resultMap[j - 1]);
}
}
return resultMap[cols - 1];
}
}```

Note: You don’t necessarily need a 2d map to store which cost O(n) space where n is the # of columns. You can just use one row to stored the result of previous row, and replace the value with the current row from left to right one by one. One thing worth mentioning is this code is more space efficient though, it has lower readability.

More information and further thoughts for minimum path sum questions can be found here.

# Leetcode: Generate Parentheses

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:

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

```public class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<String>();
if(n>0){
generateParenthesis("", n, n, result);
}
return result;
}

public void generateParenthesis(String prefix, int left, int right, List<String> result){
if(left>right){
return;
}
if(left==0){
for(int i=0;i<right;i++){
prefix+=")";
}
result.add(prefix);
return;
}
if(left<right){
generateParenthesis(prefix+")", left, right-1, result);
}
generateParenthesis(prefix+"(", left-1, right, result);
}
}```

Note: The key point of this problem is when generating parentheses, the number of left parentheses being used so far is always larger than the number of right parentheses. In the algorithm. left and right means # of parentheses not being used so far.

# Leetcode: Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

```public int climbStairs(int n) {
if (n <= 1) {
return n;
}
int[] result = new int[n + 1];
result = 1;
result = 1;
for (int i = 2; i <= n; i++) {
result[i] = result[i - 1] + result[i - 2];
}
return result[n];
}```

O(N)