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

Share

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.

    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[0] = 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()];
    }

Share

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.

  public boolean canJump(int[] A) {
    if(A==null|| A.length==0){
      return false;
    }
    boolean[] resultMap = new boolean[A.length];
    resultMap[0] = 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] = 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)

二指针问题，最大覆盖区间。从左往右扫描，维护一个覆盖区间，每扫过一个元素，就重新计算覆盖区间的边界。比如，开始时区间[start, end], 遍历A数组的过程中，不断计算A[i]+i最大值（即从i坐标开始最大的覆盖坐标），并设置这个最大覆盖坐标为新的end边界。而新的start边界则为原end+1。不断循环，直到end> n.

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

Share

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

//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[0][0] = 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

可以想成求从底部任一点出发到左上角的最小路径和 代码简洁 不会outOfBound

    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[0][0];
    }

Version 3. Bottom-Up O(n) space

在Version 2的基础上 只用2*n的数组记录数据

代码不变 只需要行数mod 2 (modulus %) 就行了

    public int minimumTotal(ArrayList < ArrayList < Integer >> triangle) {
    	if (triangle == null || triangle.size() == 0) {
    		return 0;
    	}
    	int size = triangle.size();
    	int[][] resultMap = new int[2][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[0][0];
    }

Share