算法题求解

[kaweh]

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

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

[neosfung]

动态规划，编辑距离的最简单版本

[geelaw]

一个显然的思路是 F(i, j) 等于 S 前 i 个字符中出现子序列的 L 前 j 个字符的次数。

[kaweh]

@neosfung 谢谢我去搜索学习下

[kaweh]

@neosfung 哥们 编辑距离讲的是从一个字符串转换成为另外一个字符串的最少次数 似乎和题目不符啊

[neosfung]

@kaweh 编辑距离有三种操作，删，增，改。你的需求只需要删去 s 中的字符，使得它变成 L。把编辑距离算法改一下，只留下删的操作就行了

[starqoq]

这是一个动态规划问题 f[i][j] 表示第一个串匹配到 i 且第二个串匹配到 j 的方案数量
f[i][j] = sum(f[k][j-1],k=1~i-1) (s1i s2j 相等) / 0 (不相等)

[zbw0046]

f[i][j]=f[i-1][j] +f[i-1][j-1] if s[i]=l[j] f[i-1][j] others

[kaweh]

面试官反馈：代码考察字符串找子 pattern 的数目
我去！这题是不是直接使用正则表达式得了 确定是在考察算法吗？？

[kaweh]

将 S 通过删除的方式转变为 L 则`编辑距离`就是删除`len(S)`-`len(L)`个字符 但编辑距离不是本题的结果

`暴力解法`:从 L 中选出 len(S)个字符 选出的字符的组合等于 S 则计数 1