-1

我正在尝试解决这个问题。问题是：给定一个字符串 S 和一个字符串 T，计算 S 中 T 的不同子序列的数量。

字符串的子序列是由原始字符串通过删除一些（可以是无）字符而不干扰剩余字符的相对位置而形成的新字符串。（即，“ACE”是“ABCDE”的子序列，而“AEC”不是）。

这是一个例子：S =“兔子”，T =“兔子”

答案应该是 3。

class permute:
    def __init__(self):
        self.count = 0

    def count_permute(self, s, t, i, j):
        print(i, j)
        if t in s:
            self.count += 1
            return
        if i >= len(s) or j >= len(t):
            return
        self.count_permute(s, t, i+1, j)
        if s[i] == t[j] and j == (len(t)-1):
            self.count += 1
            self.count_permute(s, t, i+1, j+1)
        else:
            self.count_permute(s, t, i+1, j+1)

    def print_count(self):
        print(self.count)

p = permute()
p.count_permute("rabbbit", "rabbit", 0, 0)
p.print_count()

通过创建矩阵，我还知道动态编程解决方案。但是我想知道这种递归方法哪里出错了？目前它正在打印 6，但答案应该是 3。

4

1 回答 1

0

该程序失败是因为它的逻辑似乎与解决问题的算法没有特别的联系。鉴于单字母变量名称和缺少注释，我很难弄清楚您的意图。

我确实理解if i >= len(s) 或 j >= len(t): return的语句——如果我们已经用完任一字符串的末尾，请停止查找。同样，在适当的支持下，函数的后半部分可以工作，但在这种情况下还不足以完成它的工作。

我没有得到第一个if操作：您发现t作为s的批发子串。计算一个子序列是正确的，但随后你就放弃了寻找。你打算如何超过给定的1（“abababab”，“ab”）？你找到第一个，数 1，然后完全退出。同样，当您提交一个测试用例时，它会失败，计算太多的用例。

我还用 ("bababababab", "aa"); 它声称有 25 个解决方案，计算幽灵并摸索指数进展。如果我删除两端的 'b' 字符，它计数为 20。这应该是您的终端计数的线索。

对于 ("aacbaaa", "aba")，它计算 31 次出现而不是实际的 6 次。

在当前代码中，您需要继续查找初始匹配项。您需要在这里进行两个递归调用（使用j和j+1）。您还需要限制那些搜索结束的过度计数。

最后，我强烈推荐一些基本的蛮力调试：打印语句中的东西来跟踪例程的进度。跟踪进入和退出、参数值和返回条件。我插入了以下跟踪语句以帮助找到我的方式：

def count_permute(self, s, t, i, j):
    print "ENTER", \
        "\ts=", s[i:], "; i=", i,\
        "\tt=", t[j:], "; j=", j

这只是一个开始。

如果您没有找到快速的解决方案，我建议您回到您编写上述代码的伪代码。在几个简单的案例中对算法进行桌面模拟，例如我提供的案例。确保您已经干净地处理了基本的递归步骤：

  1. 终止条件
  2. 检测案例
  3. 递归调用

我认为你在最后一个方面有一个不错的处理，你几乎在＃2 那里。您离可行的解决方案并不远；继续插电！

于 2016-02-25T00:29:31.020 回答