计算字符串中子序列出现的次数

Question

举个例子，假设我们有一个字符串，它是圆周率的前10位数字，3141592653，而我们要找的子序列是123。注意，这个序列在字符串中出现了两次：

3141592653
 1    2  3
   1  2  3

这是一个面试问题，我当时没能回答出来，现在想不出一个高效的算法，真让我烦恼。我觉得用简单的正则表达式应该可以做到，但像1.*2.*3这样的表达式并不能找到所有的子序列。我在Python中的简单实现（就是在每个1后面数2后面的3的数量）已经运行了一个小时，但还没完成。

Answer 1

一种方法是用两个列表，分别叫做 Ones 和 OneTwos。

然后逐个字符地查看这个字符串。

• 每当你看到数字 1 时，就在 Ones 列表里添加一个条目。
• 每当你看到数字 2 时，就去 Ones 列表里查找，并在 OneTwos 列表里添加一个条目。
• 每当你看到数字 3 时，就去 OneTwos 列表里查找，并输出一个 123。

一般情况下，这个算法会非常快，因为它只需一次遍历整个字符串，而对通常会小得多的列表进行多次遍历。不过在一些特殊情况下，它的效率会下降。比如想象一下一个字符串 111111222222333333，但每个数字都重复了几百次。

Answer 2

很棒的回答，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_cache装饰器的自顶向下解决方案（在Python 3.2及以上版本的functools中可用）

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

Answer 3

这是一个经典的动态规划问题（通常不通过正则表达式来解决）。

我简单的实现方法（在每个1后面计算每个2的3的数量）已经运行了一个小时，但还没有完成。

这是一种穷举搜索的方法，运行时间是指数级的。（我很惊讶它能运行这么久）。

---

这里有一个动态规划解决方案的建议：

递归解决方案的概述：

（抱歉描述有点长，但每一步其实都很简单，请耐心看完；-）

• 如果子序列为空，说明找到了匹配（没有数字可以匹配了！），我们返回1。

• 如果输入序列为空，说明我们的数字用完了，无法找到匹配，因此返回0。

• （序列和子序列都不为空。）

• （假设"abcdef"表示输入序列，"xyz"表示子序列。）

• 将result设置为0。

• 将result加上bcdef和xyz的匹配数量（也就是说，丢掉第一个输入数字，递归调用）。

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

  • 将result加上bcdef和yz的匹配数量（也就是说，匹配第一个子序列数字，然后递归处理剩下的子序列数字）。
    
    

• 返回result。

---

示例

这里是输入1221 / 12的递归调用示例。（子序列用粗体表示，·表示空字符串。）

---

动态规划

如果简单实现，某些（子）问题会被多次解决（例如上面示例中的· / 2）。动态规划通过记住之前解决的子问题的结果（通常在查找表中）来避免这种重复计算。

在这个特定的案例中，我们建立一个表格，包含：

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

          

我们的想法是，在相应的行/列中填写221 / 2的匹配数量。一旦完成，我们应该在单元格1221 / 12中得到最终结果。

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

• 当没有子序列数字时，我们有1个完整的匹配：

          

• 当没有序列数字时，我们无法有任何匹配：

  

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

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

  直观上这意味着“221 / 2的匹配数量包括所有的21 / 2的匹配。”

• 如果行row的序列和列col的子序列以相同的数字开头，将在[row-1][col-1]找到的值加到刚写入的[row][col]中。

  直观上这意味着“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(MN)，其中M和N分别表示序列的长度。