3571. 最短超级串 II 🔒

题目描述

给定两个字符串，s1 和 s2。返回同时包含 s1 和 s2 作为子串的最短字符串。如果有多个合法的答案，返回任意一个。

子串是字符串中连续的字符序列。

示例 1：

输入：s1 = "aba", s2 = "bab"

输出："abab"

解释：

"abab" 是同时包含 "aba" 和 "bab" 作为子串的最短字符串。

示例 2：

输入：s1 = "aa", s2 = "aaa"

输出："aaa"

解释：

"aa" 已经被包含在 "aaa" 中，所以最短超级串是 "aaa"。

提示：

1 <= s1.length <= 100
1 <= s2.length <= 100
s1 和 s2 只包含小写英文字母。

解法

方法一：枚举重叠部分

我们可以通过枚举两个字符串的重叠部分，构造一个包含 s1 和 s2 的最短字符串。

我们希望构造一个最短的字符串，使得它同时包含 s1 和 s2 作为子串。由于子串要求是连续的，因此我们尝试让一个字符串的后缀和另一个字符串的前缀重叠，从而实现拼接时长度的压缩。

具体分为三种情况：

包含关系：如果 s1 是 s2 的子串，那么 s2 本身就满足条件，返回 s2 即可；反之亦然。
s1 在前拼接 s2：我们枚举 s1 的后缀是否是 s2 的前缀，找到最大重叠部分后拼接。
s2 在前拼接 s1：我们枚举 s1 的前缀是否是 s2 的后缀，找到最大重叠部分后拼接。
无重叠：若两者无任何前后缀重叠，直接返回 s1 + s2。

我们对这两种拼接方式都尝试一遍，取较短的那个（若长度相同可返回任意一个）。

时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是 s1 和 s2 的最大长度。

Python3JavaC++GoTypeScript

class Solution:
    def shortestSuperstring(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        if m > n:
            return self.shortestSuperstring(s2, s1)
        if s1 in s2:
            return s2
        for i in range(m):
            if s2.startswith(s1[i:]):
                return s1[:i] + s2
            if s2.endswith(s1[: m - i]):
                return s2 + s1[m - i :]
        return s1 + s2

class Solution {
    public String shortestSuperstring(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        if (m > n) {
            return shortestSuperstring(s2, s1);
        }
        if (s2.contains(s1)) {
            return s2;
        }
        for (int i = 0; i < m; i++) {
            if (s2.startsWith(s1.substring(i))) {
                return s1.substring(0, i) + s2;
            }
            if (s2.endsWith(s1.substring(0, m - i))) {
                return s2 + s1.substring(m - i);
            }
        }
        return s1 + s2;
    }
}

class Solution {
public:
    string shortestSuperstring(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        if (m > n) {
            return shortestSuperstring(s2, s1);
        }
        if (s2.find(s1) != string::npos) {
            return s2;
        }
        for (int i = 0; i < m; ++i) {
            if (s2.find(s1.substr(i)) == 0) {
                return s1.substr(0, i) + s2;
            }
            if (s2.rfind(s1.substr(0, m - i)) == s2.size() - (m - i)) {
                return s2 + s1.substr(m - i);
            }
        }
        return s1 + s2;
    }
};

func shortestSuperstring(s1 string, s2 string) string {
    m, n := len(s1), len(s2)

    if m > n {
        return shortestSuperstring(s2, s1)
    }

    if strings.Contains(s2, s1) {
        return s2
    }

    for i := 0; i < m; i++ {
        if strings.HasPrefix(s2, s1[i:]) {
            return s1[:i] + s2
        }
        if strings.HasSuffix(s2, s1[:m-i]) {
            return s2 + s1[m-i:]
        }
    }

    return s1 + s2
}

function shortestSuperstring(s1: string, s2: string): string {
    const m = s1.length,
        n = s2.length;

    if (m > n) {
        return shortestSuperstring(s2, s1);
    }

    if (s2.includes(s1)) {
        return s2;
    }

    for (let i = 0; i < m; i++) {
        if (s2.startsWith(s1.slice(i))) {
            return s1.slice(0, i) + s2;
        }
        if (s2.endsWith(s1.slice(0, m - i))) {
            return s2 + s1.slice(m - i);
        }
    }

    return s1 + s2;
}

3571. 最短超级串 II 🔒

题目描述

解法

方法一：枚举重叠部分

评论