V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
kaweh
V2EX  ›  问与答

算法题求解

  •  
  •   kaweh · 2017-11-26 13:16:38 +08:00 · 2010 次点击
    这是一个创建于 2538 天前的主题,其中的信息可能已经有所发展或是发生改变。

    给定字符串 S 和 L,在字符串 S 中寻找 L 的每个字符按顺序出现在 S 中的次数 例如 S=AABBAAA L=ABA 建立下 S 的下标索引 S0=A S1=A S2=B... 可能的结果是 024 025 026 034 035 036 124 ... 136

    这题我想了很久了也不会 也搜不到相关结果 求大神指点一番

    9 条回复    2017-11-28 14:59:50 +08:00
    neosfung
        1
    neosfung  
       2017-11-26 13:38:56 +08:00 via iPhone
    动态规划,编辑距离的最简单版本
    geelaw
        2
    geelaw  
       2017-11-26 14:45:06 +08:00 via iPhone
    一个显然的思路是 F(i, j) 等于 S 前 i 个字符中出现子序列的 L 前 j 个字符的次数。
    kaweh
        3
    kaweh  
    OP
       2017-11-26 15:57:38 +08:00 via iPhone
    @neosfung 谢谢我去搜索学习下
    kaweh
        4
    kaweh  
    OP
       2017-11-26 16:18:41 +08:00 via iPhone
    @neosfung 哥们 编辑距离讲的是从一个字符串转换成为另外一个字符串的最少次数 似乎和题目不符啊
    neosfung
        5
    neosfung  
       2017-11-26 16:28:20 +08:00 via iPhone
    @kaweh 编辑距离有三种操作,删,增,改。你的需求只需要删去 s 中的字符,使得它变成 L。把编辑距离算法改一下,只留下删的操作就行了
    starqoq
        6
    starqoq  
       2017-11-26 17:41:17 +08:00 via Android
    这是一个动态规划问题 f[i][j] 表示第一个串匹配到 i 且第二个串匹配到 j 的方案数量
    f[i][j] = sum(f[k][j-1],k=1~i-1) (s1i s2j 相等) / 0 (不相等)
    zbw0046
        7
    zbw0046  
       2017-11-26 22:43:18 +08:00 via Android
    f[i][j]=f[i-1][j] +f[i-1][j-1] if s[i]=l[j] f[i-1][j] others
    kaweh
        8
    kaweh  
    OP
       2017-11-27 10:48:07 +08:00
    面试官反馈:代码考察字符串找子 pattern 的数目
    我去!这题是不是直接使用正则表达式得了 确定是在考察算法吗??
    kaweh
        9
    kaweh  
    OP
       2017-11-28 14:59:50 +08:00
    将 S 通过删除的方式转变为 L 则`编辑距离`就是删除`len(S)`-`len(L)`个字符 但编辑距离不是本题的结果

    `暴力解法`:从 L 中选出 len(S)个字符 选出的字符的组合等于 S 则计数 1
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   993 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 20:48 · PVG 04:48 · LAX 12:48 · JFK 15:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.