Easy

题目描述

给你三个字符串：s1、s2 和 s3。在一次操作中，你可以选择其中一个字符串并删除它的最右边字符。注意你不能完全清空一个字符串。

返回使字符串相等所需的最少操作次数。如果不可能使它们相等，返回 -1。

示例 1：

输入：s1 = "abc", s2 = "abb", s3 = "ab"
输出：2
解释：从 s1 和 s2 删除最右边的字符将得到三个相等的字符串。

示例 2：

输入：s1 = "dac", s2 = "bac", s3 = "cac"
输出：-1
解释：由于 s1 和 s2 的第一个字母不同，它们无法变得相等。

提示：

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

提示：

  • 计算 3 个字符串的最长公共前缀的长度。

解题思路

解题思路

这道题的关键在于理解题目要求：通过删除字符串的右端字符来使三个字符串相等。

核心观察：

  1. 由于只能删除右端字符，最终相等的字符串必然是三个字符串的公共前缀
  2. 我们需要找到三个字符串的最长公共前缀
  3. 如果最长公共前缀为空，说明无法使三个字符串相等，返回 -1
  4. 否则，每个字符串需要删除的字符数就是：字符串长度 - 最长公共前缀长度

算法步骤：

  1. 找到三个字符串长度的最小值，这是公共前缀的最大可能长度
  2. 从左到右比较三个字符串的每一位，直到找到第一个不相等的位置
  3. 如果公共前缀长度为 0，返回 -1
  4. 否则返回三个字符串各自需要删除的字符数之和

时间复杂度为 O(min(len1, len2, len3))，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int findMinimumOperations(string s1, string s2, string s3) {
        int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
        int minLen = min({n1, n2, n3});
        
        int commonPrefixLen = 0;
        for (int i = 0; i < minLen; i++) {
            if (s1[i] == s2[i] && s2[i] == s3[i]) {
                commonPrefixLen++;
            } else {
                break;
            }
        }
        
        if (commonPrefixLen == 0) {
            return -1;
        }
        
        return (n1 - commonPrefixLen) + (n2 - commonPrefixLen) + (n3 - commonPrefixLen);
    }
};

class Solution:
    def findMinimumOperations(self, s1: str, s2: str, s3: str) -> int:
        n1, n2, n3 = len(s1), len(s2), len(s3)
        min_len = min(n1, n2, n3)
        
        common_prefix_len = 0
        for i in range(min_len):
            if s1[i] == s2[i] == s3[i]:
                common_prefix_len += 1
            else:
                break
        
        if common_prefix_len == 0:
            return -1
        
        return (n1 - common_prefix_len) + (n2 - common_prefix_len) + (n3 - common_prefix_len)

public class Solution {
    public int FindMinimumOperations(string s1, string s2, string s3) {
        int n1 = s1.Length, n2 = s2.Length, n3 = s3.Length;
        int minLen = Math.Min(Math.Min(n1, n2), n3);
        
        int commonPrefixLen = 0;
        for (int i = 0; i < minLen; i++) {
            if (s1[i] == s2[i] && s2[i] == s3[i]) {
                commonPrefixLen++;
            } else {
                break;
            }
        }
        
        if (commonPrefixLen == 0) {
            return -1;
        }
        
        return (n1 - commonPrefixLen) + (n2 - commonPrefixLen) + (n3 - commonPrefixLen);
    }
}

var findMinimumOperations = function(s1, s2, s3) {
    const n1 = s1.length, n2 = s2.length, n3 = s3.length;
    const minLen = Math.min(n1, n2, n3);
    
    let commonPrefixLen = 0;
    for (let i = 0; i < minLen; i++) {
        if (s1[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(min(n1, n2, n3))，其中 n1、n2、n3 分别是三个字符串的长度
空间复杂度O(1)，只使用常数额外空间

相关题目