问一道Google面经

求问一道在网上看到的Google家面经：

求string str1中含有string

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

c”

只想到brute force，有没有其它好办法？

muybienw 发表于 2016-1-20 07:11
上面帖子的代码格式有问题... 重新贴一下

用三个指针就行了，时间复杂度O(n^2)，空间复杂度O(1)

1. public class ShortestSequence {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 System.out.println(getShortestSequence("acbacbc", "abc"));
   
5.         }
   
6.         public static int getShortestSequence(String s1, String s2) {
   
7.                 if (s1.length() < s2.length()) {
   
8.                         return Integer.MAX_VALUE;
   
9.                 }
   
10.                 int res = Integer.MAX_VALUE;
    
11.                 for (int i = 0; i < s1.length(); i++) {
    
12.                         if (s1.charAt(i) == s2.charAt(0)) {
    
13.                                 int j = i;
    
14.                                 int k = 0;
    
15.                                 while (j < s1.length() && k < s2.length()) {
    
16.                                         if (s1.charAt(j) == s2.charAt(k)) {
    
17.                                                 j++;
    
18.                                                 k++;
    
19.                                         } else {
    
20.                                                 j++;
    
21.                                         }
    
22.                                 }
    
23.                                 if (k == s2.length()) {
    
24.                                         res = Math.min(res, j - i);
    
25.                                 }
    
26.                         }
    
27.                 }
    
28.                
    
29.                
    
30.                 return res;
    
31.         }
    
32. }
    

复制代码

用dp写了一下，欢迎讨论～

1. <font size="1">    <span style="color: rgb(204, 120, 50);">public </span>String <span style="color: rgb(255, 198, 109);">findShortest</span>(String a<span style="color: rgb(204, 120, 50);">, </span>String b){
   
2.         <span style="color: rgb(204, 120, 50);">if</span>(a==<span style="color: rgb(204, 120, 50);">null </span>|| b==<span style="color: rgb(204, 120, 50);">null </span>|| a.length()==<span style="color: rgb(104, 151, 187);">0 </span>|| b.length()==<span style="color: rgb(104, 151, 187);">0</span>) <span style="color: rgb(204, 120, 50);">throw new </span>IllegalArgumentException()<span style="color: rgb(204, 120, 50);">;
   
3. </span><span style="color: rgb(204, 120, 50);">
   
4. </span><span style="color: rgb(204, 120, 50);">        int </span>lena = a.length()<span style="color: rgb(204, 120, 50);">, </span>lenb = b.length()<span style="color: rgb(204, 120, 50);">;
   
5. </span><span style="color: rgb(204, 120, 50);">        int</span>[][] dp = <span style="color: rgb(204, 120, 50);">new int</span>[lenb][lena]<span style="color: rgb(204, 120, 50);">;
   
6. </span><span style="color: rgb(204, 120, 50);">
   
7. </span><span style="color: rgb(204, 120, 50);">        for</span>(<span style="color: rgb(204, 120, 50);">int </span>i=<span style="color: rgb(104, 151, 187);">0</span><span style="color: rgb(204, 120, 50);">; </span>i<lenb<span style="color: rgb(204, 120, 50);">; </span>i++){
   
8.             <span style="color: rgb(204, 120, 50);">char </span>bc = b.charAt(i)<span style="color: rgb(204, 120, 50);">;
   
9. </span><span style="color: rgb(204, 120, 50);">            for</span>(<span style="color: rgb(204, 120, 50);">int </span>j=<span style="color: rgb(104, 151, 187);">0</span><span style="color: rgb(204, 120, 50);">; </span>j<lena<span style="color: rgb(204, 120, 50);">; </span>j++){
   
10.                 <span style="color: rgb(204, 120, 50);">char </span>ac = a.charAt(j)<span style="color: rgb(204, 120, 50);">;
    
11. </span><span style="color: rgb(204, 120, 50);">                </span>dp[i][j] = Integer.<span style="color: rgb(152, 118, 170); font-style: italic;">MAX_VALUE</span><span style="color: rgb(204, 120, 50);">;
    
12. </span><span style="color: rgb(204, 120, 50);">
    
13. </span><span style="color: rgb(204, 120, 50);">                if</span>(ac==bc){
    
14.                     <span style="color: rgb(204, 120, 50);">if</span>(i==<span style="color: rgb(104, 151, 187);">0</span>) dp[i][j] = <span style="color: rgb(104, 151, 187);">1</span><span style="color: rgb(204, 120, 50);">;
    
15. </span><span style="color: rgb(204, 120, 50);">                    else </span>{
    
16.                         <span style="color: rgb(204, 120, 50);">for </span>(<span style="color: rgb(204, 120, 50);">int </span>t = <span style="color: rgb(104, 151, 187);">0</span><span style="color: rgb(204, 120, 50);">; </span>t < j<span style="color: rgb(204, 120, 50);">; </span>t++) {
    
17.                             <span style="color: rgb(204, 120, 50);">if </span>(dp[i - <span style="color: rgb(104, 151, 187);">1</span>][t] == Integer.<span style="color: rgb(152, 118, 170); font-style: italic;">MAX_VALUE</span>) <span style="color: rgb(204, 120, 50);">continue;
    
18. </span><span style="color: rgb(204, 120, 50);">                            else </span>dp[i][j] = Math.<span style="font-style: italic;">min</span>(dp[i][j]<span style="color: rgb(204, 120, 50);">, </span>dp[i - <span style="color: rgb(104, 151, 187);">1</span>][t] + j - t)<span style="color: rgb(204, 120, 50);">;
    
19. </span><span style="color: rgb(204, 120, 50);">                        </span>}
    
20.                     }
    
21.                 }
    
22.             }
    
23.         }
    
24. 
    
25.         <span style="color: rgb(204, 120, 50);">int </span>min = Integer.<span style="color: rgb(152, 118, 170); font-style: italic;">MAX_VALUE</span><span style="color: rgb(204, 120, 50);">;
    
26. </span><span style="color: rgb(204, 120, 50);">        int </span>end = -<span style="color: rgb(104, 151, 187);">1</span><span style="color: rgb(204, 120, 50);">;
    
27. </span><span style="color: rgb(204, 120, 50);">
    
28. </span><span style="color: rgb(204, 120, 50);">        for</span>(<span style="color: rgb(204, 120, 50);">int </span>j=<span style="color: rgb(104, 151, 187);">0</span><span style="color: rgb(204, 120, 50);">; </span>j<lena<span style="color: rgb(204, 120, 50);">; </span>j++){
    
29.             <span style="color: rgb(204, 120, 50);">if</span>(dp[lenb-<span style="color: rgb(104, 151, 187);">1</span>][j] < min) {
    
30.                 min = dp[lenb-<span style="color: rgb(104, 151, 187);">1</span>][j]<span style="color: rgb(204, 120, 50);">;
    
31. </span><span style="color: rgb(204, 120, 50);">                </span>end = j<span style="color: rgb(204, 120, 50);">;
    
32. </span><span style="color: rgb(204, 120, 50);">            </span>}
    
33.         }
    
34. 
    
35. <span style="color: rgb(128, 128, 128);">//        System.out.println(end);
    
36. </span><span style="color: rgb(128, 128, 128);">//        System.out.println(min);
    
37. </span><span style="color: rgb(128, 128, 128);">
    
38. </span><span style="color: rgb(128, 128, 128);">        </span><span style="color: rgb(204, 120, 50);">if</span>(end==-<span style="color: rgb(104, 151, 187);">1</span>) <span style="color: rgb(204, 120, 50);">return </span><span style="color: rgb(106, 135, 89);">"no match!"</span><span style="color: rgb(204, 120, 50);">;
    
39. </span><span style="color: rgb(204, 120, 50);">        return </span>a.substring(end-min+<span style="color: rgb(104, 151, 187);">1</span><span style="color: rgb(204, 120, 50);">, </span>end+<span style="color: rgb(104, 151, 187);">1</span>)<span style="color: rgb(204, 120, 50);">;
    
40. </span><span style="color: rgb(204, 120, 50);">    </span>}</font>

复制代码

dp可破之。。

类似于 LC 76. Minimum Window Substring。 但需要保持order。

我怎么觉得得用dp做？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

kidzlike 发表于 2016-1-20 06:11
我怎么觉得得用dp做？

能详细讲讲么，怎么用dp？

上面帖子的代码格式有问题... 重新贴一下

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

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

pattern对应到i位置，string对应到j位置时，shortest substring的长度，Int_Max表示不存在