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

Question

例如,让字符串为pi的前10位,3141592653子序列为123.请注意,序列出现两次:

3141592653
 1    2  3
   1  2  3

这是一个我无法回答的面试问题,我想不出一个有效的算法而且它让我烦恼.我觉得应该可以使用一个简单的正则表达式,但是1.*2.*3不要返回每个子序列.我在Python中的天真实现(在每个1之后计算每个2的3个)已经运行了一个小时而且还没有完成.

Answer 1

这是一个经典的动态编程问题(通常不使用正则表达式解决).

我天真的实现(每1个后每2个计算3个)已经运行了一个小时而且没有完成.

这将是一种在指数时间内运行的详尽搜索方法.(我很惊讶它跑了好几个小时).

以下是动态编程解决方案的建议:

递归解决方案的大纲:

(对于长篇描述道歉,但每一步都很简单所以请耐心等待;-)

• 如果子序列为空,则找到匹配项(没有数字匹配!),我们返回1

• 如果输入序列为空,我们已经耗尽了数字,并且无法找到匹配,因此我们返回0

• (序列和子序列都不是空的.)

• (假设" abcdef "表示输入序列," xyz "表示子序列.)

• 设为result0

• 添加到bcdef和xyzresult的匹配数(即丢弃第一个输入数字并递归)

• 如果前两位数匹配,即a = x

  • 添加到bcdef和yzresult的匹配数(即匹配第一个子序列数并递归剩余的子序列数)
    
    

• 返回 result

例

下面是输入1221 /递归调用的说明12.(粗体字的子序列,·表示空字符串.)

动态编程

如果天真地实施,则一些(子)问题被多次解决(·//2,例如在上图中).动态编程通过记住先前解决的子问题(通常在查找表中)的结果来避免这种冗余计算.

在这种特殊情况下,我们设置了一个表

• [序列长度+ 1]行,和
• [子序列的长度+ 1]列:

          

我们的想法是,我们应该在比赛的多项填补国内221/ 2在相应的行/列.一旦这样做,我们应该在电池1221 /最终的解决方案12.

我们开始使用我们立即知道的内容填充表格("基本案例"):

• 当没有剩下子序列数字时,我们有1个完全匹配:

          

• 如果没有剩下序列数字,我们就不能有任何匹配:

  

然后,我们按照以下规则从上到下/从左到右填充表格:

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

  直观上,这意味着"匹配的221 /数2包括用于21 /所有匹配2 ".

• 如果行的行序列和列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表示序列的长度.

Answer 2

很棒的答案,aioobe!为了补充你的答案,Python中的一些可能的实现:

# straightforward, naïve solution; too slow!

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

# top-down solution using explicit memoization

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)

# top-down solution using the lru_cache decorator
# available from functools in python >= 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)

# bottom-up, dynamic programming solution using a lookup table

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]

# bottom-up, dynamic programming solution using a single array

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

一种方法是使用两个列表.给他们打电话Ones和OneTwos.

逐个字符地浏览字符串.

• 每当看到数字时1,在Ones列表中输入一个条目.
• 每当看到数字时2,请浏览Ones列表并在列表中添加条目OneTwos.
• 每当看到数字时3,请浏览OneTwos列表并输出a 123.

在一般情况下,算法将非常快,因为它是单个通过字符串并且多次通过通常会小得多的列表.然而,病理性病例会杀死它.想象一下像一个字符串111111222222333333,但每个数字重复数百次.