问一道Google面经

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

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

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. }
    

复制代码

bobzhang2004 发表于 2016-3-9 12:54
用三个指针就行了，时间复杂度O(n^2)，空间复杂度O(1)

bingo!
感觉这样做是最好的
dp要O(n) space 时间复杂度还是一样的

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

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

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

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