查找字符串Y的子字符串X的最长子序列
我知道如何使用动态规划来解决 <罢工> 大多数 给定两个字符串的最长公共子串或最长公共子串。然而，对于字符串Y的子串X的最长子序列问题，我很难找到一个解决方案。
- 查找字符串X的所有子序列并按长度desc排序；
- 遍历排序的子序列，如果当前子序列是Y的子字符串，则返回子序列。
它可以工作，但运行时间可能会很糟糕。假设X中的所有字符都是唯一的，那么有2^m个子群，其中m是X的长度，我认为检查一个字符串是否是Y的子串需要O(n)，其中n是Y的长度，所以总的运行时间是O(n*2^m)。
更好的方法是通过DP吗？
Y: 'BACDBDCD'
X: 'ABCD'
共有1个答案
这里有两种方法（这两种方法都具有多项式时间复杂度）。
1。生成Y的所有子字符串（有O(m^2)这样的子字符串）。对于每个子字符串，检查它是否是X的子序列（可以使用贪婪算法在线性时间内完成）。该算法的时间复杂度O(n*m^2)已经不是那么糟糕了。
2。如果速度不够快，则可以使用动态编程实现O(n*m)时间复杂度。让我们定义F(i,j)=在X中的I-th位置和y中的J-th位置结束的最长答案。转换如下：
f(i + 1, j) = max(f(i + 1, j), f(i, j)) //skip this character in X
if X[i] == Y[j] //add this character to current answer
f(i + 1, j + 1) = max(f(i + 1, j + 1), f(i, j) + 1)
对于所有有效的i和j，f的初始值为0。答案是f(n,j)中所有有效j的最大值。
-
http://articles.leetcode.com/2011/11/lengton-palindromic-substring-part-i.html 我处理这个问题的领域是用java编写代码，使用简单的强力解决方案，然后使用o(n2)方法，没有额外的空间，就像现在这样。http://www.geeksforgeeks.org/lengte-palindromic-substring-set
-
我如何在O(N**2)个时间内完成它？
-
问题内容： 我有在另一个主题上找到的这段代码，但是该代码按连续字符而不是字母顺序对子字符串进行排序。如何按字母顺序更正？它打印出来了，我想打印。谢谢 ps：我是python的初学者 问题答案： 尝试更改此： 对此： 这将显示您的示例输入字符串。代码更简单，因为您正试图解决一个更简单的问题:-)
-
问题内容： 我正在尝试从Java字符串中找到所有三个字母子字符串。 例如，从字符串“ example string”中，我应该得到“ exa”，“ xam”，“ amp”，“ mpl”，“ ple”，“ str”，“ tri”，“ rin”，“ ing”。 我尝试使用Java正则表达式“（[[a-zA-Z]）{3}”，但仅得到“ exa”，“ mpl”，“ str”，“ ing”。 有人可以告诉我
-
问题 你需要搜索一个字符串，并返回匹配的起始位置或匹配值本身。 解决方案 有几种使用正则表达式的方法来实现这个功能。其中一些方法被称为 RegExp 模式或对象还有一些方法被称为 String 对象。 RegExp 对象 第一种方式是在 RegExp 模式或对象中调用 test 方法。test 方法返回一个布尔值： match = /sample/.test("Sample text") # =>
-
问题 你想在一条消息中查找某个关键字第一次或最后一次出现的位置。 解决方案 分别使用 JavaScript 的 indexOf() 和 lastIndexOf() 方法查找字符串第一次和最后一次出现的位置。语法: string.indexOf searchstring, start message = "This is a test string. This has a repeat or two