查找字符串中子序列的出现次数

Question

例如，让字符串是pi的前10位，3141592653，子序列是123。请注意，序列发生两次：

3141592653
 1    2  3
   1  2  3

这是一个面试问题，我无法回答，我想不出一个有效的算法，它困扰着我。我觉得应该可以使用一个简单的regex，但是像1.*2.*3这样的regex并不返回每个子序列。我在Python中的天真实现（在每1个之后，每2个计算3）已经运行了一个小时，但还没有完成。

Answer 1

一种方法是列出两个清单。称它们为Ones和OneTwos。

一个字符一个字符地检查字符串。

• 每当看到数字1时，在Ones列表中创建一个条目。
• 每当看到数字2时，请浏览Ones列表并向OneTwos列表添加一个条目。
• 每当看到数字3时，请浏览OneTwos列表并输出123。

在一般情况下，该算法将非常快速，因为它是通过字符串的一次传递和通过通常小得多的列表的多次传递。但病理病例会杀死它。想象一个类似111111222222333333的字符串，但是每个数字重复数百次。

Answer 2

这是一个经典的dynamic programming问题（通常不使用正则表达式解决）。

My naive implementation (count the 3's for each 2 after each 1) has been running for an hour and it's not done.

这将是一个在指数时间内运行的穷举搜索方法。（不过，我很惊讶它能持续几个小时）。

---

下面是一个动态编程解决方案的建议：

递归解决方案的大纲：

（很抱歉描述太长了，但每一步都很简单，请耐心等待；-）

• 如果子序列为空，则会找到匹配项（没有数字可供匹配！）我们返回1

• 如果输入序列为空，则表示我们的位数已耗尽，无法找到匹配项，因此返回0

• （序列和子序列都不是空的。）

• （假设“abcdef”表示输入序列，“xyz”表示子序列。

• 将result设置为0

• 在result中添加bcdef和xyz的匹配数（即放弃第一个输入数字并递归）

• 如果前两个数字匹配，即a=x

  • 在result中添加bcdef和yz的匹配数（即匹配第一个子序列数字并在其余子序列数字上递归）
    
    
    

• 返回result

---

示例

下面是对输入1221/12的递归调用的说明。（子序列为粗体，·表示空字符串。）

---

动态规划

如果简单地实现，一些（子）问题会被多次解决（例如上图中的·/2）。动态编程通过记住以前解决的子问题（通常在查找表中）的结果来避免这种冗余计算。

在这种情况下，我们用

• [序列长度+1]行，以及
• [子序列长度+1]列：

我们的想法是在相应的行/列中填写221/2的匹配数。一旦完成，我们应该在1221号细胞中找到最终的解决方案。

我们开始用我们立即知道的内容填充表（“基本情况”）：

• 当没有留下子序列数字时，我们有1个完全匹配：

• 如果没有序列号，则不能有任何匹配项：

  

然后，我们按照以下规则从上到下/从左到右填充表：

• 在单元格[行][列]中，写入在[行-1][col]中找到的值。

  直观地说，这意味着221/2的匹配数包括21/2的所有匹配

• 如果行行处的序列和列列处的subseq以相同的数字开始，则将在[行-1][列-1]处找到的值添加到刚刚写入的值[行[列]。

  直观地说，这意味着“1221/12的匹配数也包括221/12的所有匹配数”

最终结果如下：

右下角单元格的值确实是2。

---

在代码中

不是用Python写的，（我道歉）。

class SubseqCounter {

    String seq, subseq;
    int[][] tbl;

    public SubseqCounter(String seq, String subseq) {
        this.seq = seq;
        this.subseq = subseq;
    }

    public int countMatches() {
        tbl = new int[seq.length() + 1][subseq.length() + 1];

        for (int row = 0; row < tbl.length; row++)
            for (int col = 0; col < tbl[row].length; col++)
                tbl[row][col] = countMatchesFor(row, col);

        return tbl[seq.length()][subseq.length()];
    }

    private int countMatchesFor(int seqDigitsLeft, int subseqDigitsLeft) {
        if (subseqDigitsLeft == 0)
            return 1;

        if (seqDigitsLeft == 0)
            return 0;

        char currSeqDigit = seq.charAt(seq.length()-seqDigitsLeft);
        char currSubseqDigit = subseq.charAt(subseq.length()-subseqDigitsLeft);

        int result = 0;

        if (currSeqDigit == currSubseqDigit)
            result += tbl[seqDigitsLeft - 1][subseqDigitsLeft - 1];

        result += tbl[seqDigitsLeft - 1][subseqDigitsLeft];

        return result;
    }
}

---

复杂性

这种“填表”方法的一个好处是，计算复杂度是微不足道的。每一个单元的工作量是恒定的，我们有序列行的长度和子序列的长度柱。复杂度为O（M N），其中M和N表示序列的长度。

Answer 3

很好的回答，aioobe！为了补充您的答案，Python中的一些可能实现：

1）简单、天真的解决方案；太慢！

def num_subsequences(seq, sub):
    if not sub:
        return 1
    elif not seq:
        return 0
    result = num_subsequences(seq[1:], sub)
    if seq[0] == sub[0]:
        result += num_subsequences(seq[1:], sub[1:])
    return result

2）自上而下使用显式备忘录的解决方案

def num_subsequences(seq, sub):
    m, n, cache = len(seq), len(sub), {}
    def count(i, j):
        if j == n:
            return 1
        elif i == m:
            return 0
        k = (i, j)
        if k not in cache:
            cache[k] = count(i+1, j) + (count(i+1, j+1) if seq[i] == sub[j] else 0)
        return cache[k]
    return count(0, 0)

3）使用lru缓存装饰器的自上而下解决方案（可从python中的functools>；=3.2获得）

from functools import lru_cache

def num_subsequences(seq, sub):
    m, n = len(seq), len(sub)
    @lru_cache(maxsize=None)
    def count(i, j):
        if j == n:
            return 1
        elif i == m:
            return 0
        return count(i+1, j) + (count(i+1, j+1) if seq[i] == sub[j] else 0)
    return count(0, 0)

4）使用查找表的自下而上的动态编程解决方案

def num_subsequences(seq, sub):
    m, n = len(seq)+1, len(sub)+1
    table = [[0]*n for i in xrange(m)]
    def count(iseq, isub):
        if not isub:
            return 1
        elif not iseq:
            return 0
        return (table[iseq-1][isub] +
               (table[iseq-1][isub-1] if seq[m-iseq-1] == sub[n-isub-1] else 0))
    for row in xrange(m):
        for col in xrange(n):
            table[row][col] = count(row, col)
    return table[m-1][n-1]

5）使用单个数组的自下而上的动态编程解决方案

def num_subsequences(seq, sub):
    m, n = len(seq), len(sub)
    table = [0] * n
    for i in xrange(m):
        previous = 1
        for j in xrange(n):
            current = table[j]
            if seq[i] == sub[j]:
                table[j] += previous
            previous = current
    return table[n-1] if n else 1