Medium

题目描述

给你三个字符串 a、b 和 c，你的任务是找到一个长度最短的字符串，使得这三个字符串都是它的子串。

如果有多个这样的字符串，返回字典序最小的那一个。

返回表示问题答案的字符串。

注意：

  • 如果字符串 a 在字典序上小于字符串 b（长度相同），那么在第一个 a 和 b 不同的位置上，a 中的字母在字母表中出现得比 b 中对应的字母早。
  • 子串是字符串中字符的连续序列。

示例 1：

输入：a = "abc", b = "bca", c = "aaa"
输出："aaabca"
解释：我们可以看出 "aaabca" 包含所有给定的字符串：a = ans[2...4], b = ans[3..5], c = ans[0..2]。可以证明结果字符串的长度至少为 6，而 "aaabca" 是字典序最小的一个。

示例 2：

输入：a = "ab", b = "ba", c = "aba"
输出："aba"
解释：我们可以看出字符串 "aba" 包含所有给定的字符串：a = ans[0..1], b = ans[1..2], c = ans[0..2]。由于 c 的长度为 3，结果字符串的长度至少为 3。可以证明 "aba" 是字典序最小的一个。

约束条件：

  • 1 <= a.length, b.length, c.length <= 100
  • a、b、c 仅由小写英文字母组成

解题思路

这是一个字符串合并问题。我们需要找到包含三个给定字符串作为子串的最短字符串。

核心思路：

  1. 如果一个字符串已经包含另一个字符串作为子串，那么我们不需要额外添加字符
  2. 对于两个字符串的合并，我们尝试找到最大重叠部分，即第一个字符串的后缀与第二个字符串的前缀的最大匹配
  3. 由于只有三个字符串，我们可以枚举所有可能的排列（3! = 6种），对每种排列计算最短合并结果

算法步骤：

  1. 定义合并函数：给定两个字符串，找到将它们合并的最短方式
  2. 枚举三个字符串的所有排列（abc, acb, bac, bca, cab, cba）
  3. 对每个排列，依次合并字符串
  4. 比较所有结果，选择长度最短且字典序最小的

合并策略：

  • 如果字符串B已经是字符串A的子串，直接返回A
  • 否则，找到A的后缀与B的前缀的最大重叠，然后将B的剩余部分追加到A后面

时间复杂度为O(n²)，其中n是字符串的最大长度，空间复杂度为O(n)。

代码实现

class Solution {
public:
    string minimumString(string a, string b, string c) {
        vector<string> strs = {a, b, c};
        vector<int> perm = {0, 1, 2};
        string result = a + b + c; // 最坏情况
        
        do {
            string merged = merge(merge(strs[perm[0]], strs[perm[1]]), strs[perm[2]]);
            if (merged.length() < result.length() || 
                (merged.length() == result.length() && merged < result)) {
                result = merged;
            }
        } while (next_permutation(perm.begin(), perm.end()));
        
        return result;
    }
    
private:
    string merge(string s1, string s2) {
        // 如果s2已经是s1的子串
        if (s1.find(s2) != string::npos) return s1;
        // 如果s1已经是s2的子串
        if (s2.find(s1) != string::npos) return s2;
        
        // 找到最大重叠
        int maxOverlap = 0;
        int n1 = s1.length(), n2 = s2.length();
        
        // s1的后缀与s2的前缀重叠
        for (int i = 1; i <= min(n1, n2); i++) {
            if (s1.substr(n1 - i) == s2.substr(0, i)) {
                maxOverlap = i;
            }
        }
        
        return s1 + s2.substr(maxOverlap);
    }
};

class Solution:
    def minimumString(self, a: str, b: str, c: str) -> str:
        from itertools import permutations
        
        def merge(s1, s2):
            # 如果s2已经是s1的子串
            if s2 in s1:
                return s1
            # 如果s1已经是s2的子串
            if s1 in s2:
                return s2
            
            # 找到最大重叠
            max_overlap = 0
            n1, n2 = len(s1), len(s2)
            
            # s1的后缀与s2的前缀重叠
            for i in range(1, min(n1, n2) + 1):
                if s1[-i:] == s2[:i]:
                    max_overlap = i
            
            return s1 + s2[max_overlap:]
        
        strs = [a, b, c]
        result = a + b + c  # 最坏情况
        
        for perm in permutations(range(3)):
            merged = merge(merge(strs[perm[0]], strs[perm[1]]), strs[perm[2]])
            if len(merged) < len(result) or (len(merged) == len(result) and merged < result):
                result = merged
        
        return result

public class Solution {
    public string MinimumString(string a, string b, string c) {
        string[] strs = {a, b, c};
        int[] perm = {0, 1, 2};
        string result = a + b + c; // 最坏情况
        
        do {
            string merged = Merge(Merge(strs[perm[0]], strs[perm[1]]), strs[perm[2]]);
            if (merged.Length < result.Length || 
                (merged.Length == result.Length && string.Compare(merged, result) < 0)) {
                result = merged;
            }
        } while (NextPermutation(perm));
        
        return result;
    }
    
    private string Merge(string s1, string s2) {
        // 如果s2已经是s1的子串
        if (s1.Contains(s2)) return s1;
        // 如果s1已经是s2的子串
        if (s2.Contains(s1)) return s2;
        
        // 找到最大重叠
        int maxOverlap = 0;
        int n1 = s1.Length, n2 = s2.Length;
        
        // s1的后缀与s2的前缀重叠
        for (int i = 1; i <= Math.Min(n1, n2); i++) {
            if (s1.Substring(n1 - i) == s2.Substring(0, i)) {
                maxOverlap = i;
            }
        }
        
        return s1 + s2.Substring(maxOverlap);
    }
    
    private bool NextPermutation(int[] nums) {
        int i = nums.Length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i < 0) return false;
        
        int j = nums.Length - 1;
        while (nums[j] <= nums[i]) j--;
        
        (nums[i], nums[j]) = (nums[j], nums[i]);
        Array.Reverse(nums, i + 1, nums.Length - i - 1);
        return true;
    }
}

var minimumString = function(a, b, c) {
    function merge(s1, s2) {
        if (s1.includes(s2)) return s1;
        if (s2.includes(s1)) return s2;
        
        let maxOverlap = 0;
        let result = s1 + s2;
        
        for (let i = 1; i <= Math.min(s1.length, s2.length); i++) {
            if (s1.endsWith(s2.substring(0, i))) {
                maxOverlap = i;
            }
        }
        
        if (maxOverlap > 0) {
            result = s1 + s2.substring(maxOverlap);
        }
        
        return result;
    }
    
    function mergeThree(x, y, z) {
        return merge(merge(x, y), z);
    }
    
    let strings = [a, b, c];
    let candidates = [];
    
    for (let perm of [[0,1,2], [0,2,1], [1,0,2], [1,2,0], [2,0,1], [2,1,0]]) {
        candidates.push(mergeThree(strings[perm[0]], strings[perm[1]], strings[perm[2]]));
    }
    
    candidates.sort((x, y) => {
        if (x.length !== y.length) {
            return x.length - y.length;
        }
        return x.localeCompare(y);
    });
    
    return candidates[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n²)
空间复杂度O(n)

其中 n 是输入字符串的最大长度。时间复杂度主要来源于字符串匹配操作，空间复杂度主要用于存储中间结果。

相关题目