代碼面試最常用的10大算法(四)

動态程式設計主要用來解決如下技術問題：

• An instance is solved using the solutions for smaller instances；
• 對于一個較小的執行個體，可能需要許多個解決方案；
• 把較小執行個體的解決方案存儲在一個表中，一旦遇上，就很容易解決；
• 附加空間用來節省時間。

上面所列的爬台階問題完全符合這四個屬性，是以，可以使用動态程式設計來解決：

1 2 3 4 5 6 7 8 9 10 11 12

public static int[] A = new int[100]; public static int f3(int n) { if (n <= 2) A[n]= n; if (A[n] > 0) return A[n]; else A[n] = f3(n-1) + f3(n-2); //store results so only calculate once! return A[n]; }

一些基于動态程式設計的算法：

編輯距離

From Wiki:

In computer science, edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other.

There are three operations permitted on a word: replace, delete, insert. For example, the edit distance between “a” and “b” is 1, the edit distance between “abc” and “def” is 3. This post analyzes how to calculate edit distance by using dynamic programming.

Key Analysis

Let dp[i][j] stands for the edit distance between two strings with length i and j, i.e., word1[0,...,i-1] and word2[0,...,j-1].

There is a relation between dp[i][j] and dp[i-1][j-1]. Let’s say we transform from one string to another. The first string has length i and it’s last character is “x”; the second string has length j and its last character is “y”. The following diagram shows the relation.

1. if x == y, then dp[i][j] == dp[i-1][j-1]
2. if x != y, and we insert y for word1, then dp[i][j] = dp[i][j-1] + 1
3. if x != y, and we delete x for word1, then dp[i][j] = dp[i-1][j] + 1
4. if x != y, and we replace x with y for word1, then dp[i][j] = dp[i-1][j-1] + 1
5. When x!=y, dp[i][j] is the min of the three situations.

Initial condition:

dp[i][0] = i, dp[0][j] = j

Java Code

After the analysis above, the code is just a representation of it.

public static int minDistance(String word1, String word2) { int len1 = word1.length(); int len2 = word2.length();   // len1+1, len2+1, because finally return dp[len1][len2] int[][] dp = new int[len1 + 1][len2 + 1];   for (int i = 0; i <= len1; i++) { dp[i][0] = i; }   for (int j = 0; j <= len2; j++) { dp[0][j] = j; }   //iterate though, and check last char for (int i = 0; i < len1; i++) { char c1 = word1.charAt(i); for (int j = 0; j < len2; j++) { char c2 = word2.charAt(j);   //if last two chars equal if (c1 == c2) { //update dp value for +1 length dp[i + 1][j + 1] = dp[i][j]; } else { int replace = dp[i][j] + 1; int insert = dp[i][j + 1] + 1; int delete = dp[i + 1][j] + 1;   int min = replace > insert ? insert : replace; min = delete > min ? min : delete; dp[i + 1][j + 1] = min; } } }   return dp[len1][len2]; }

  最長回文子串   Finding the longest palindromic substring is a classic problem of coding interview. In this post, I will summarize 3 different solutions for this problem.

1. Naive Approach

Naively, we can simply examine every substring and check if it is palindromic. The time complexity is O(n^3). If this is submitted to LeetCode onlinejudge, an error message will be returned – “Time Limit Exceeded”. Therefore, this approach is just a start, we need better algorithm.

public static String longestPalindrome1(String s) {   int maxPalinLength = 0; String longestPalindrome = null; int length = s.length();   // check all possible sub strings for (int i = 0; i < length; i++) { for (int j = i + 1; j < length; j++) { int len = j - i; String curr = s.substring(i, j + 1); if (isPalindrome(curr)) { if (len > maxPalinLength) { longestPalindrome = curr; maxPalinLength = len; } } } }   return longestPalindrome; }   public static boolean isPalindrome(String s) {   for (int i = 0; i < s.length() - 1; i++) { if (s.charAt(i) != s.charAt(s.length() - 1 - i)) { return false; } }   return true; }

2. Dynamic Programming

Let s be the input string, i and j are two indices of the string.

Define a 2-dimension array “table” and let table[i][j] denote whether substring from i to j is palindrome.

Start condition:

table[i][i] == 1;
table[i][i+1] == 1  => s.charAt(i) == s.charAt(i+1) 
      

Changing condition:

table[i][j] == 1 => table[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j)
      

Time O(n^2) Space O(n^2)

public static String longestPalindrome2(String s) { if (s == null) return null;   if(s.length() <=1) return s;   int maxLen = 0; String longestStr = null;   int length = s.length();   int[][] table = new int[length][length];   //every single letter is palindrome for (int i = 0; i < length; i++) { table[i][i] = 1; } printTable(table);   //e.g. bcba //two consecutive same letters are palindrome for (int i = 0; i <= length - 2; i++) { if (s.charAt(i) == s.charAt(i + 1)){ table[i][i + 1] = 1; longestStr = s.substring(i, i + 2); } } printTable(table); //condition for calculate whole table for (int l = 3; l <= length; l++) { for (int i = 0; i <= length-l; i++) { int j = i + l - 1; if (s.charAt(i) == s.charAt(j)) { table[i][j] = table[i + 1][j - 1]; if (table[i][j] == 1 && l > maxLen) longestStr = s.substring(i, j + 1); } else { table[i][j] = 0; } printTable(table); } }   return longestStr; } public static void printTable(int[][] x){ for(int [] y : x){ for(int z: y){ System.out.print(z + " "); } System.out.println(); } System.out.println("------"); }

Given an input, we can use printTable method to examine the table after each iteration. For example, if input string is “dabcba”, the final matrix would be the following:

1 0 0 0 0 0 
0 1 0 0 0 1 
0 0 1 0 1 0 
0 0 0 1 0 0 
0 0 0 0 1 0 
0 0 0 0 0 1 
      

From the table, we can clear see that the longest string is in cell table[1][5].

3. Simple Algorithm

Time O(n^2), Space O(1)

public String longestPalindrome(String s) { if (s.isEmpty()) { return null; }   if (s.length() == 1) { return s; }   String longest = s.substring(0, 1); for (int i = 0; i < s.length(); i++) { // get longest palindrome with center of i String tmp = helper(s, i, i); if (tmp.length() > longest.length()) { longest = tmp; }   // get longest palindrome with center of i, i+1 tmp = helper(s, i, i + 1); if (tmp.length() > longest.length()) { longest = tmp; } }   return longest; }   // Given a center, either one letter or two letter, // Find longest palindrome public String helper(String s, int begin, int end) { while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) { begin--; end++; } return s.substring(begin + 1, end); }

4. Manacher’s Algorithm

Manacher’s algorithm is much more complicated to figure out, even though it will bring benefit of time complexity of O(n).

單詞分割

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

For example, given

s = “leetcode”,

dict = ["leet", "code"].

Return true because “leetcode” can be segmented as “leet code”.

1. Naive Approach

This problem can be solve by using a naive approach, which is trivial. A discussion can always start from that though.

public class Solution { public boolean wordBreak(String s, Set<String> dict) { return wordBreakHelper(s, dict, 0); }   public boolean wordBreakHelper(String s, Set<String> dict, int start){ if(start == s.length()) return true;   for(String a: dict){ int len = a.length(); int end = start+len;   //end index should be <= string length if(end > s.length()) continue;   if(s.substring(start, start+len).equals(a)) if(wordBreakHelper(s, dict, start+len)) return true; }   return false; } }

Time: O(2^n)

2. Dynamic Programming

The key to solve this problem by using dynamic programming approach:

• Define an array t[] such that t[i]==true => 0-(i-1) can be segmented using dictionary
• Initial state t[0] == true

public class Solution { public boolean wordBreak(String s, Set<String> dict) { boolean[] t = new boolean[s.length()+1]; t[0] = true; //set first to be true, why? //Because we need initial state   for(int i=0; i<s.length(); i++){ //should continue from match position if(!t[i]) continue;   for(String a: dict){ int len = a.length(); int end = i + len; if(end > s.length()) continue;   if(t[end]) continue;   if(s.substring(i, end).equals(a)){ t[end] = true; } } }   return t[s.length()]; } }

Time: O(string length * dict size)

One tricky part of this solution is the case:

INPUT: "programcreek", ["programcree","program","creek"]. 
      

最大的子數組

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],

the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Naive Solution

A wrong solution. Simply iterate the array like the following will not work.

public class Solution { public int maxSubArray(int[] A) { int sum = 0; int maxSum = Integer.MIN_VALUE;   for (int i = 0; i < A.length; i++) { sum += A[i]; maxSum = Math.max(maxSum, sum);   if (sum < 0) sum = 0; }   return maxSum; } }

Dynamic Programming Solution

We should ignore the sum of the previous n-1 elements if nth element is greater than the sum.

public class Solution {
	public int maxSubArray(int[] A) {
		int max = A[0];
		int[] sum = new int[A.length];
		sum[0] = A[0];
 
		for (int i = 1; i < A.length; i++) {
			sum[i] = Math.max(A[i], sum[i - 1] + A[i]);
			max = Math.max(max, sum[i]);
		}
 
		return max;
	}
}