前几天的 骨骼店面

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

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

感谢分享！祝好运！
貌似可以先根据B求所有可行路径（子序列），然后在A上求从头到尾的最短路径。B上通过枚举或者dfs（O(2^n)）构造可行子序列，可行子序列可以再构造一个trie方便后面查询。A上DP求最短路（O(n * m), 其他最短路径算法应该再快些)。

您好！
本帖隐藏的内容需要积分高于 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

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

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

这题我想用greedy从A中匹配尽量多的B中的元素（用反证法可以证出这样肯定最少），然后双指针扫A和B,B扫完了说明A匹配完了，B指针reset成0匹配A的下一段。代码也很简单（时间复杂度是O(m + n)）:

1. public int minConstruct0(String a, String b) {
   
2.         int i = 0;
   
3.         int count = 0;
   
4.         while (i < a.length()) {
   
5.             int j = 0;
   
6.             int prev = i;
   
7.             while (i < a.length() && j < b.length()) {
   
8.                 if (a.charAt(i) == b.charAt(j)) {
   
9.                     i++;
   
10.                     j++;
    
11.                 } else {
    
12.                     j++;
    
13.                 }
    
14.             }
    
15.             if (prev == i) return -1;
    
16.             count++;
    
17.         }
    
18.         return count;
    
19.     }

复制代码

补充内容 (2018-8-17 02:20):
时间复杂度应该是O(mn).

您好！
本帖隐藏的内容需要积分高于 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

xxw289 发表于 2018-8-10 11:11
这题我想用greedy从A中匹配尽量多的B中的元素（用反证法可以证出这样肯定最少），然后双指针扫A和B,B扫完了 ...

感谢！受教了

xiaocase 发表于 2018-8-10 11:16
感谢！受教了

不敢不敢，我也是先写了个O(n^3)的DP优化了一个小时想出来的。。。