这是一个创建于 2547 天前的主题，其中的信息可能已经有所发展或是发生改变。
给定字符串 S 和 L，在字符串 S 中寻找 L 的每个字符按顺序出现在 S 中的次数 例如 S=AABBAAA L=ABA 建立下 S 的下标索引 S0=A S1=A S2=B... 可能的结果是 024 025 026 034 035 036 124 ... 136
这题我想了很久了也不会 也搜不到相关结果 求大神指点一番
 |
1
neosfung 2017-11-26 13:38:56 +08:00 via iPhone
动态规划，编辑距离的最简单版本
|
 |
2
geelaw 2017-11-26 14:45:06 +08:00 via iPhone
一个显然的思路是 F(i, j) 等于 S 前 i 个字符中出现子序列的 L 前 j 个字符的次数。
|
 |
4
kaweh OP @neosfung 哥们 编辑距离讲的是从一个字符串转换成为另外一个字符串的最少次数 似乎和题目不符啊
|
|
5
neosfung 2017-11-26 16:28:20 +08:00 via iPhone
@kaweh 编辑距离有三种操作，删，增，改。你的需求只需要删去 s 中的字符，使得它变成 L。把编辑距离算法改一下，只留下删的操作就行了
|
 |
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 (不相等) |
 |
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
|
|
8
kaweh OP 面试官反馈：代码考察字符串找子 pattern 的数目
我去！这题是不是直接使用正则表达式得了 确定是在考察算法吗？？ |
|
9
kaweh OP 将 S 通过删除的方式转变为 L 则`编辑距离`就是删除`len(S)`-`len(L)`个字符 但编辑距离不是本题的结果
`暴力解法`:从 L 中选出 len(S)个字符 选出的字符的组合等于 S 则计数 1 |
Select Language