谷狗新鲜店面

没太看明白

我理解是说str1是重复的BABA这种，
str2删了部分之后如果可以变成BABA或者BA这种，拼几次可以拼成str1么？

我觉得可以kmp找str1的最小重复节，比如是BA
再用这个match str2，看str2有多少个BA，
如果str2的subsequence有BABA，那就一次，只有BA就两次，什么都没有就不能拼

zzwcsong 发表于 2018-12-13 12:47
一点想法，如果修改后的s2 (记作ms2)要能重构成s1，那么ms2一定要是s1的前缀。从所有可能构成s1前缀的ms2出 ...

我如果采用greedy， BABB，ABB，ABB，AB， 也是四次。我们能不能举出一个例子，说明我这个greedy要比你那个次数多呢 讨论哈～

所以题目里的删掉一些character，每次删掉的是一样的吗？
比如CAB第一次匹配删掉C用AB，那么之后的几次都只能用AB吗

pengbomuzzy 发表于 2018-12-21 09:48
我如果采用greedy， BABB，ABB，ABB，AB， 也是四次。我们能不能举出一个例子，说明我这个greedy要比你那 ...

我理解的题意是只能用同一个修改后的str2 copy?如果是你说的这样，会更复杂些..

zzwcsong 发表于 2018-12-21 11:50
我理解的题意是只能用同一个修改后的str2 copy?如果是你说的这样，会更复杂些..

哦哦 我明白了 突然觉得题意不是特别清楚哈 只能靠楼主来解释了

1. Naive : O(mn)
2. optimized: O((m+n)*logm)
3. Further optimized: O(n+m^2)

stellari 发表于 2018-12-10 04:00
题目说能够从str2中移走任意数目的字符，也就是说能用来匹配str的不是str2的substring，而是（非连续的） ...

这个问题最有的解法可以做到O(m+n)
首先生成str2的next数组，next[i][j]表示从str2的i位置开始，第一个j+'a'字符出现的位置，这个过程应该是O(m)
然后在去匹配str1的前缀的时候，可以用next数组来做，每一次匹配都是O(1)的，总的是O(n)
和利口其二气应该是类似的

用javascript 写的brute force, 觉得应该可以加上memorization 应该就可以了？

1. function makeStr(strA, strB) {
   
2.     let lst = generateAllSubsequneceOfAString(strB);
   
3.     lst.shift(); // Remove the first empty list
   
4.     return backtrack(strA, lst, 0);
   
5. }
   
6. 
   
7. function backtrack(strA, lst, numCopies) {
   
8.     if (strA === "") {
   
9.         return numCopies;
   
10.     }
    
11.     let returnedCopies = Infinity;
    
12.     for (let i = 0; i < lst.length; i++) {
    
13.         if (strA.startsWith(lst[i])) {
    
14.             returnedCopies = Math.min(backtrack(strA.substring(lst[i].length), lst, numCopies + 1), returnedCopies);
    
15.         }   
    
16.     }
    
17.     return returnedCopies;
    
18. }
    
19. 
    
20. // Essentially powerset
    
21. function generateAllSubsequneceOfAString(str) {
    
22.     let ps = [[]];
    
23.     let lst = str.split("");
    
24.     for (let i = 0; i < lst.length; i++) {
    
25.         for (let j = 0, len = ps.length; j < len; j++) {
    
26.             ps = ps.concat(ps[j].concat(lst[i]));
    
27.         }
    
28.     }
    
29.     return ps;
    
30. }
    
31. 
    
32. console.log(makeStr("BABA", "BA")); // 2
    
33. console.log(makeStr("BABA", "CAB")); // 3 => CABCABCAB => BABA
    
34. console.log(makeStr("ABCCA", "ACB")); // 4
    

复制代码

楼主看不见题> <可不可以求复制一下题的内容。。。感激不尽！！

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

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