Generate all sub-sequences of length K
From http://introcs.cs.princeton.edu/java/23recursion/Subsequence.java.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class Subsequence {
public static void print(String prefix, String remaining, int k) {
if(k>prefix.length()+remaining.length())return;
if (k == 0) {
System.out.println(prefix);
return;
}
if (remaining.length() == 0) return;
//pick the first character in remaining, combine with remaining of remaining
//this is to sequentially build up the subsequence until the k length
print(prefix + remaining.charAt(0), remaining.substring(1), k-1);
//then another possible is to skip one character in remaining, and combine with rest of remaining
print(prefix, remaining.substring(1), k);
}
public static void main(String[] args) {
String s = "abcd";
int k =3;
print("", s, k);
}
}
|
Longest common subsequence
This is a basic DP problem. code can be very concise after understanding it.
https://www.youtube.com/watch?v=NnD96abizww
http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/
The following code example is form http://introcs.cs.princeton.edu/java/96optimization/LCS.java.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 | package string;
public class LCS {
public static String lcs(String s1,String s2) {
int M = s1.length();
int N = s2.length();
// opt[i][j] = length of LCS of x[i..M] and y[j..N]
int[][] opt = new int[M+1][N+1];
// compute length of LCS and all subproblems via dynamic programming
//this is the basic formula:
//this is also working from back to start. usually it is from start to end
for (int i = M-1; i >= 0; i--) {
for (int j = N-1; j >= 0; j--) {
if (s1.charAt(i) == s2.charAt(j))
opt[i][j] = opt[i+1][j+1] + 1;
else
opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
}
}
//version from start to end
/*
for (int i = 1; i <M; i++) {
for (int j = 1; j <N; j++) {
if (s1.charAt(i) == s2.charAt(j))
opt[i][j] = opt[i-1][j-1] + 1;
else
opt[i][j] = Math.max(opt[i-1][j], opt[i][j-1]);
}
}
*/
// recover LCS itself and print it to standard output
StringBuilder sb = new StringBuilder();
int i = 0, j = 0;
while(i < M && j < N) {
if (s1.charAt(i) == s2.charAt(j)) {
sb.append(s1.charAt(i));
i++;
j++;
}
else if (opt[i+1][j] >= opt[i][j+1]) i++;//means it is from i++
else j++;//means it is from j++
}
return sb.toString();
}
}
|
Longest Common SubString
similar but easier than common subsequence, still use 2D matrix, compare if m[i,j]=(s1.charAt(i)==s2.charAt(j)) and go diagonally until it is not true. repeat that process to find longest one.
No comments:
Post a Comment