Distinct Subsequences
Given a string S and a string T, count the number of distinct sub sequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
這兩個題目很相似，狀態方程是f(i, j) = f(i - 1, j) + S[i] == T[j]? f(i - 1, j - 1) : 0 Where f(i, j) is the number of distinct sub-sequence for T[0:j] in S[0:i].
數組初始情況是第一列全部是1，代表T字符串是空串，S和自己做匹配。實現代碼如下：
1 public class DistinctSubsequences {
2 public int numDistinct(String S, String T) {
3 int[][] f = new int[S.length() + 1][T.length() + 1];
4 for (int k = 0; k < S.length(); k++)
5 f[k][0] = 1;
6 for (int i = 1; i <= S.length(); i++) {
7 for (int j = 1; j <= T.length(); j++) {
8 if (S.charAt(i - 1) == T.charAt(j - 1)) {
9 f[i][j] += f[i - 1][j] + f[i - 1][j - 1];
10 } else {
11 f[i][j] += f[i - 1][j];
12 }
13 }
14 }
15 return f[S.length()][T.length()];
16 }
17 }
Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
1 public class EditDistance {
2 public int minDistance(String word1, String word2) {
3 if (word1.length() == 0 || word2.length() == 0)
4 return word1.length() == 0 ? word2.length() : word1.length();
5 int[][] arr = new int[word2.length() + 1][word1.length() + 1];
6 for (int i = 0; i <= word1.length(); i++) {
7 arr[0][i] = i;
8 }
9 for (int j = 0; j <= word2.length(); j++) {
10 arr[j][0] = j;
11 }
12 for (int i = 0; i < word1.length(); i++) {
13 for (int j = 0; j < word2.length(); j++) {
14 if (word1.charAt(i) == word2.charAt(j)) {
15 arr[j + 1][i + 1] = arr[j][i];
16 } else {
17 int dis = Math.min(arr[j][i + 1], arr[j + 1][i]);
18 arr[j + 1][i + 1] = Math.min(arr[j][i], dis) + 1;
19 }
20 }
21 }
22 return arr[word2.length()][word1.length()];
23 }
24 }