时间戳

首页 > 解决方案 > 如何从两个字符串中生成最短的字符串

python-3.x - 如何从两个字符串中生成最短的字符串

问题描述

我想编写一个函数来从两个字符串 A、B 中返回最短的字符串 C，并确保字符串 A、B 是 C 的子字符串。但关键是 A 的长度不必比 B 长，例如：

A: 'abcd', B: 'cde' = > C: 'abcde' # c,d 重复
A: 'abcd', B: 'ecd' = > C: 'abcdecd' #没有字符重复所以C是A + B
A: 'abc', B: 'cdeab' = > C: 'cdeabc'
A: 'bce', B: 'eabc' = > C: 'eabce' #eabcd的长度是5，bceabc的长度是6
A: '', B: 'abc' = > C: 'abc'
A: 'abc', B: '' = > C: 'abc'

我有以下功能，但似乎不正确

def checksubstring(A, B):
    if not A or not B: return A if not B else B
    index, string = 0, ''
    for i, c in enumerate(A):
        index = index + 1 if c == B[index] else 0
        string += c
    return string + B[index:]

标签： python-3.x

解决方案

您可以从最后备份寻找匹配项，例如：

代码：

def shortest_substring(a, b):

    def checksubstring(a, b):
        if not a or not b:
            return b or a

        for i in range(1, len(b)):
            if a[len(a) - i:] == b[:i]:
                return a + b[i:]
        return a + b

    x = checksubstring(a, b)
    y = checksubstring(b, a)
    return x if len(x) <= len(y) else y

测试代码：

results = [
    {'A': 'abcd', 'B': 'cde', 'C': 'abcde'},
    {'A': 'abcd', 'B': 'ecd', 'C': 'abcdecd'},
    {'A': 'abc', 'B': 'cdeab', 'C': 'cdeabc'},
    {'A': 'bce', 'B': 'eabc', 'C': 'eabce'},
    {'A': '', 'B': 'abc', 'C': 'abc'},
    {'A': 'abc', 'B': '', 'C': 'abc'},
]

for result in results:
    assert result['C'] == shortest_substring(result['A'], result['B'])

推荐阅读