📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: shanshanlate
跳转到指定楼层
上一主题 下一主题
收起左侧

谷狗新鲜店面

🔗
John1993 2018-12-14 10:44:58 | 只看该作者
全局:
没太看明白

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

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

使用道具 举报

🔗
pengbomuzzy 2018-12-21 09:48:13 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
Hexess 2018-12-21 11:11:53 | 只看该作者
全局:
所以题目里的删掉一些character,每次删掉的是一样的吗?
比如CAB第一次匹配删掉C用AB,那么之后的几次都只能用AB吗
回复

使用道具 举报

🔗
zzwcsong 2018-12-21 11:50:08 | 只看该作者
全局:
pengbomuzzy 发表于 2018-12-21 09:48
我如果采用greedy, BABB,ABB,ABB,AB, 也是四次。我们能不能举出一个例子,说明我这个greedy要比你那 ...

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

使用道具 举报

🔗
pengbomuzzy 2018-12-22 01:41:56 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
yliu2008 2018-12-22 07:31:54 | 只看该作者
全局:
1. Naive : O(mn)
2. optimized: O((m+n)*logm)
3. Further optimized: O(n+m^2)
回复

使用道具 举报

🔗
bdhmwzfa 2018-12-25 16:14:58 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
yeou110 2018-12-27 14:46:36 | 只看该作者
全局:
用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. function backtrack(strA, lst, numCopies) {
  7.     if (strA === "") {
  8.         return numCopies;
  9.     }
  10.     let returnedCopies = Infinity;
  11.     for (let i = 0; i < lst.length; i++) {
  12.         if (strA.startsWith(lst[i])) {
  13.             returnedCopies = Math.min(backtrack(strA.substring(lst[i].length), lst, numCopies + 1), returnedCopies);
  14.         }   
  15.     }
  16.     return returnedCopies;
  17. }

  18. // Essentially powerset
  19. function generateAllSubsequneceOfAString(str) {
  20.     let ps = [[]];
  21.     let lst = str.split("");
  22.     for (let i = 0; i < lst.length; i++) {
  23.         for (let j = 0, len = ps.length; j < len; j++) {
  24.             ps = ps.concat(ps[j].concat(lst[i]));
  25.         }
  26.     }
  27.     return ps;
  28. }

  29. console.log(makeStr("BABA", "BA")); // 2
  30. console.log(makeStr("BABA", "CAB")); // 3 => CABCABCAB => BABA
  31. console.log(makeStr("ABCCA", "ACB")); // 4
复制代码
回复

使用道具 举报

🔗
mumudi 2018-12-27 15:01:13 | 只看该作者
全局:
楼主看不见题> <可不可以求复制一下题的内容。。。感激不尽!!
回复

使用道具 举报

🔗
copperface 2019-1-1 14:18:54 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表