美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 章子怡的好后妈人设崩塌? 继女被曝和奶奶生活
  • 好着呢!杨幂刘恺威参加女儿班级活动 一家人同框
  • 美图:我们用户大多是“白富美” 不愁赚钱
  • 网红面包店深夜发声明 承认面粉过期
  • 手机以换壳为本?华为余承东:没有创新才这么干
  • 腾讯二把手悄然交接 一人拿到大笔钱一人掌握更大权
  • 那些恐怖电影中的角色生活中原来长这样
  • 《神奇女侠》女神新手办亮相:脸崩了 但美腿还能玩一年
  • 再进华夏中原 小米之家郑州第二店正式开业
  • 中国人的睡眠:西藏最幸福 海南最可怜
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3030|回复: 8

    内推面经 -问一道算法题max length of subsequence string matching subs- 唐人社区| ...

    [复制链接]

    9

    主题

    370

    帖子

    388

    积分

    中级会员

    Rank: 3Rank: 3

    积分
    388
    QQ
    发表于 2016-10-3 20:20:34 | 显示全部楼层 |阅读模式
    分享到:
    {$content}

    唐人社区-北美华人论坛-内推面经版-问一道算法题max length of subsequence string matching subs


      JobHunting
    标 题: 问一道算法题max length of subsequence string matching subs


    昨天做了道challenge的题,输入两个String, a and b, 要求返回能够满足(
    subsequence of a) == (substring of b)的最大length。a和b的characters都是a-z。
    我的做法代码复杂而且时间
    复杂度也感觉不好。为了不误导大家,大牛先试试有没有好的解法,我再抛砖。

    --
    Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
    Would you capture it or just let it slip?


    新浪微博官方账号】美国省钱快报FunInUSA : 每日滚动更新美国市场折扣资讯微商进货首选资讯渠道。
    回复 百度谷歌雅虎搜狗搜搜有道360奇虎

    举报

    15

    主题

    86

    帖子

    122

    积分

    注册会员

    Rank: 2

    积分
    122
    QQ
    发表于 2016-10-3 21:09:06 | 显示全部楼层
    JobHunting
    标  题: Re: 问一道算法题max length of subsequence string matching


    这样说来dp可以解决?但我遇到的是不是2 substring match, 是subsequence matches
    substring。
    2 substring match f(i,j)=f(i-1)(j-1)+1
    subsequence matches substring, 难道要遍历row(i-1)?   f(i,j)=Max(f(i-1,0)...
    .f(i-1,j-1))+1
    这样一来就是O(m*n*n)了,与dfs没区别了。

    不过好像每个row去掉所有0,都是递增序列,可能可以找最后的值 f(i,j) = f(i-1, x
    ) ( x=max(0, j-1) and f(i-1, x)>0).
    如果用一个一维array来记录所有row最大值, 应该可以吧。我试试。

    【 在 hardpack (hardpack) 的大作中提到: 】
    : 这个?
    : https://en.m.wikipedia.org/wiki/Longest_common_substring_problem
    : 面试要问这个,多半是来找茬的。




    --
    Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
    Would you capture it or just let it slip?

    25

    主题

    86

    帖子

    136

    积分

    注册会员

    Rank: 2

    积分
    136
    QQ
    发表于 2016-10-3 23:03:27 | 显示全部楼层
    JobHunting
    标  题: Re: 问一道算法题max length of subsequence string matching subs


    subsequance 和substring有什么区别?
    如果是longest common substring,好像是用二维dp来解?
    --

    23

    主题

    90

    帖子

    139

    积分

    注册会员

    Rank: 2

    积分
    139
    QQ
    发表于 2016-10-3 23:12:41 | 显示全部楼层
    JobHunting
    标  题: 问一道算法题max length of subsequence string matching subs


    昨天做了道challenge的题,输入两个String, a and b, 要求返回能够满足(
    subsequence of a) == (substring of b)的最大length。a和b的characters都是a-z。
    我的做法代码复杂而且时间
    复杂度也感觉不好。为了不误导大家,大牛先试试有没有好的解法,我再抛砖。

    --
    Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
    Would you capture it or just let it slip?

    15

    主题

    91

    帖子

    116

    积分

    注册会员

    Rank: 2

    积分
    116
    QQ
    发表于 2016-10-3 23:47:57 | 显示全部楼层
    JobHunting
    标  题: Re: 问一道算法题max length of subsequence string matching


    Subsequence 是指可以删除任意一些characters后的string (保持原顺序)

    https://en.wikipedia.org/wiki/Subsequence


    【 在 laoqiu (老Q) 的大作中提到: 】
    : subsequance 和substring有什么区别?
    : 如果是longest common substring,好像是用二维dp来解?



    --
    Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
    Would you capture it or just let it slip?

    20

    主题

    100

    帖子

    149

    积分

    注册会员

    Rank: 2

    积分
    149
    QQ
    发表于 2016-10-4 00:10:27 | 显示全部楼层
    JobHunting
    标  题: Re: 问一道算法题max length of subsequence string matching


    试了一下DP,一维array记录所有row最大值不行,必须找最后的值 f(i,j) = f(i-1, x
    ) ( x=max(0, j-1) and f(i-1, x)>0). 可以用存一个index list, 用binary search,
    O(m*n*log(m)) 。 我觉得这个题还是直接用dfs好了,最坏情况是b里很多duplicate,
    O(m*n*n)。

    【 在 coldknight (冷骑士) 的大作中提到: 】
    : 这样说来dp可以解决?但我遇到的是不是2 substring match, 是subsequence
    matches
    :  substring。
    : 2 substring match f(i,j)=f(i-1)(j-1)+1
    : subsequence matches substring, 难道要遍历row(i-1)?   f(i,j)=Max(f(i-1,0).
    ..
    : .f(i-1,j-1))+1
    : 这样一来就是O(m*n*n)了,与dfs没区别了。
    : 不过好像每个row去掉所有0,都是递增序列,可能可以找最后的值 f(i,j) = f(i-1,
    x
    : ) ( x=max(0, j-1) and f(i-1, x)>0).
    : 如果用一个一维array来记录所有row最大值, 应该可以吧。我试试。


    --
    Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
    Would you capture it or just let it slip?

    28

    主题

    101

    帖子

    156

    积分

    注册会员

    Rank: 2

    积分
    156
    QQ
    发表于 2016-10-4 00:18:07 | 显示全部楼层
    JobHunting
    标  题: Re: 问一道算法题max length of subsequence string matching


    今天返回来一看这题,马上O(m*n) dp写出了。状态太重要了。

    【 在 coldknight (冷骑士) 的大作中提到: 】
    : 试了一下DP,一维array记录所有row最大值不行,必须找最后的值 f(i,j) = f(i-1,
    x
    : ) ( x=max(0, j-1) and f(i-1, x)>0). 可以用存一个index list, 用binary
    search,
    :  O(m*n*log(m)) 。 我觉得这个题还是直接用dfs好了,最坏情况是b里很多
    duplicate,
    :  O(m*n*n)。
    : matches
    : ..
    :  x



    --
    Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
    Would you capture it or just let it slip?

    24

    主题

    1204

    帖子

    2371

    积分

    金牌会员

    Rank: 6Rank: 6

    积分
    2371
    QQ
    发表于 2016-10-25 21:43:11 | 显示全部楼层
    鼎力支持!!

    0

    主题

    1035

    帖子

    2069

    积分

    金牌会员

    Rank: 6Rank: 6

    积分
    2069
    发表于 2016-10-29 20:34:21 | 显示全部楼层
    顶起顶起顶起
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -问一道算法题max length of subsequence string matching subs- 唐人社区| ...帖子由网友提供或转载于网络,若发布的内推面经 -问一道算法题max length of subsequence string matching subs- 唐人社区| ...侵犯了您的权益,请联系我们.
    Sasa.com

    Copyright ©2011 FunInUSA.NET All Right Reserved.  Powered by Discuz! X3.0 小黑屋

    本站信息均由会员发表,不代表美国华人网FunInUSA|唐人社区的立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA|唐人社区

    安全联盟认证 安全联盟认证

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