G面经prepare: Maximum Subsequence in Another String's Order - neverlandly - 博客园

G面经prepare: Maximum Subsequence in Another String's Order - neverlandly - 博客园

求string str1中含有string str2 order的 subsequence 的最小长度

举个例子： str1 = "acbacbc" str2="abc", 那么最小subsequence长度应该是4， 对应的subsequence是“acbc”

DP做法：dp[i][j]定义为pattern对应到i位置，string对应到j位置时，shortest substring的长度，Int_Max表示不存在

 5       public String findShortest(String a, String b){
 6             if(a==null || b==null || a.length()==0 || b.length()==0) throw new IllegalArgumentException();
 7 
 8             int lena = a.length(), lenb = b.length();
 9             int[][] dp = new int[lenb][lena];
10 
11             for(int i=0; i<lenb; i++){
12                 char bc = b.charAt(i);
13                 for(int j=0; j<lena; j++){
14                     char ac = a.charAt(j);
15                     dp[i][j] = Integer.MAX_VALUE;
16 
17                     if(ac==bc){
18                         if(i==0) dp[i][j] = 1;
19                         else {
20                             for (int t = 0; t < j; t++) {
21                                 if (dp[i - 1][t] == Integer.MAX_VALUE) continue;
22                                 else dp[i][j] = Math.min(dp[i][j], dp[i - 1][t] + j - t);
23                             }
24                         }
25                     }
26                 }
27             }
28 
29             int min = Integer.MAX_VALUE;
30             int end = -1;
31 
32             for(int j=0; j<lena; j++){
33                 if(dp[lenb-1][j] < min) {
34                     min = dp[lenb-1][j];
35                     end = j;
36                 }
37             }
38 
39 
40             if(end==-1) return "no match!";
41             return a.substring(end-min+1, end+1);
42     }

http://www.1point3acres.com/bbs/thread-166355-1-1.html
暴力就是O(n^2):
遍历str1,如果某个char i和str2的第一个char相同，就从i开始往后遍历所有字符，直到找到str2对应的sequence，或者走完str1,由于这里是同时递增遍历str1,str2，所以时间复杂度是O(n); 然后接着从i + 1开始遍历str1.总的复杂度是O(n^2). 实际跟strStr类似，那个的复杂度是O(mn),现在条件更复杂，谨慎怀疑一般的做法是否能到O(mn)。

-- Extend: the order doesn't matter
Read full article from G面经prepare: Maximum Subsequence in Another String's Order - neverlandly - 博客园