string - 不考虑字符顺序的最长匹配子串

Question

我找不到以下假设面试问题的答案:

给定两个长度为 N 的字符串序列，你如何找到不考虑顺序的匹配子串的最大长度。

例如，给定 seq1 = "ABCDEFG" 和 seq2 = "DBCAPFG"，最大长度窗口为 4。(ABCD来自 seq1 和来自 seq2 的 DBCA。

Answer 1

这是一个 O(n) 的解决方案(假设固定的字母表大小和 O(1) 字典访问)。

使用单个频率表，对 seq1 中的字符向上计数，对 seq2 中的字符向下计数。如果这个直方图再次取相同的值，我们将有一个匹配窗口(因为这意味着我们必须有相同数量的中间字符)。

因此我们使用字典来存储直方图的先前值。

Python 实现:

def find_window(seq1,seq2):
    """Yield length of matching windows"""
    D={} # Dictionary with key=histogram, value = first position where this happens
    H=[0]*26 # H[x] is count of x in seq1 - count of x in seq2
    D[tuple(H)]=-1
    for i,(a,b) in enumerate(zip(seq1,seq2)):
        a=ord(a)-ord('A')
        b=ord(b)-ord('A') 
        H[a]+=1
        H[b]-=1
        key=tuple(H)
        if key in D:
            yield i-D[key]
        if key not in D:
            D[key]=i

print max(find_window("ABCDEFG","DBCAPFG"))

如果你有一个更大的字母表，你可以使用类似的技术只存储一个散列值而不是完整的直方图。例如，您可以简单地为每个字符选择一个随机代码，然后为 seq 中的每个字母添加代码，或者为 seq2 中的字母减去代码。

如果发生哈希冲突，您将需要第二次检查建议的匹配项是否正确。