前几天的 骨骼店面

oo小天使oo 发表于 2018-8-10 08:06
我的思路是dp 有不对的地方求地里小伙伴们指点~
dp = A的前i个字符用B拼出的最少次数
首先全部设为Integ ...

我觉得  “B.indexOf(A.substring(j, i)) > 0” 这里有问题。
比如 String A = "abcbdad" ，String B = "abcd"
那么最优构成方案应该是 abc*+*b*d+a**d, return 3
在判断 "bd"这个substring时，B.indexOf（"bd"） = -1, 然而这里“bd”是可以由B挖掉两个空而得到的。

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

ljl.lee 发表于 2018-8-10 08:44
感谢分享！祝好运！
貌似可以先根据B求所有可行路径（子序列），然后在A上求从头到尾的最短路径。B上通过 ...

我用的就是DFS求所有可行解，但是没有在中间记录可行子序列。
面之前听说狗家重视交流所以写代码的时候一直在BB，每写一行就讲半天，浪费了一些时间。
现在有点后悔，应该多点时间写代码的，后面想到优化都没时间说。

xiaocase 发表于 2018-8-10 08:41
我觉得  “B.indexOf(A.substring(j, i)) > 0” 这里有问题。
比如 String A = "abcbdad" ，String B =  ...

呀~~~我题目没读清楚 原来中间也可以挖哈哈哈 谢谢楼主指出！

可不可以用一个hashmap存B中character和对应的顺序值
例如 B是“ABCD“” 那么hashmap中 A-1 B-2 C-3 D-4
然后遍历A “ABCACAD”  用一个variable存储所需B的个数
遍历到的char从hashmap中取到他的顺序 然后遍历下一个的时候查看是否下一个的值比上一个大
大的话顺序就是对的可以通过一个B获得
小的话就需要一个新的B
遍历中如果遇到不hashmap存在的key就表示不存在构成方案 返回false或者-1 否则的话返回true或者variable的值
原题和follow up时间复杂度均为O(n)

这题我想用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).

oo小天使oo 发表于 2018-8-10 10:31
可不可以用一个hashmap存B中character和对应的顺序值
例如 B是“ABCD“” 那么hashmap中 A-1 B-2 C-3 D-4
...

感觉没问题哎
完蛋了完蛋了 居然有O(N)的解法
我用的DFS 时间复杂度高的可怕
凉了凉了

oo小天使oo 发表于 2018-8-10 10:31
可不可以用一个hashmap存B中character和对应的顺序值
例如 B是“ABCD“” 那么hashmap中 A-1 B-2 C-3 D-4
...

感觉没问题哎
完蛋了完蛋了 居然有O(N)的解法
我用的DFS 时间复杂度高的可怕
凉了凉了

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

感谢！受教了

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

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