标签: 字符串
难度: Easy
给你三个字符串 s1、s2 和 s3。 你可以根据需要对这三个字符串执行以下操作 任意次数 。
在每次操作中，你可以选择其中一个长度至少为 2 的字符串 并删除其 最右位置上 的字符。
如果存在某种方法能够使这三个字符串相等，请返回使它们相等所需的 最小 操作次数；否则，返回 -1。
示例 1：
输入：s1 = "abc"，s2 = "abb"，s3 = "ab" 输出：2 解释：对 s1 和 s2 进行一次操作后，可以得到三个相等的字符串。 可以证明，不可能用少于两次操作使它们相等。
示例 2：
输入：s1 = "dac"，s2 = "bac"，s3 = "cac" 输出：-1 解释：因为 s1 和 s2 的最左位置上的字母不相等，所以无论进行多少次操作，它们都不可能相等。因此答案是 -1 。
提示：
1 <= s1.length, s2.length, s3.length <= 100s1、s2 和 s3 仅由小写英文字母组成。运行时间: 27 ms
内存: 16.1 MB
class Solution:
def findMinimumOperations(self, s1: str, s2: str, s3: str) -> int:
i = 0
while i < min(len(s1), len(s2), len(s3)):
if s1[i] == s2[i] == s3[i]:
i += 1
else:
break
return len(s1) + len(s2) + len(s3) - 3 * i if i else -1
此题解通过检查三个字符串s1, s2, s3的公共前缀来解决问题。首先，通过一个循环比较所有字符串在同一位置的字符是否相同，如果相同，则继续检查下一个字符；如果不同，或任一字符串的长度被耗尽，则停止循环。循环结束后，如果存在公共前缀（即i>0），则计算将三个字符串剪切到公共前缀长度所需的操作次数，这等于三个字符串的总长度减去三倍的公共前缀长度。如果没有公共前缀（i == 0），则直接返回-1，表示无法通过剪切使三个字符串相等。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def findMinimumOperations(self, s1: str, s2: str, s3: str) -> int:
i = 0
# 检查三个字符串的公共前缀
while i < min(len(s1), len(s2), len(s3)):
if s1[i] == s2[i] == s3[i]:
i += 1
else:
break
# 如果存在公共前缀，计算变为相同字符串所需的最小操作次数
return len(s1) + len(s2) + len(s3) - 3 * i if i else -1
在题解中，通过使用`min(len(s1), len(s2), len(s3))`作为循环的终止条件，确保了比较过程不会超出任何一个字符串的长度。这意味着在每个字符串的共同长度范围内检查字符是否相等。一旦达到任何一个字符串的结束或者发现不匹配的字符，循环就会停止。这种方法确保了算法处理不同长度字符串的能力，只关注可能的最长公共前缀。
题解中当公共前缀长度为0时返回-1，是基于题目的设定，即只通过剪切字符串的操作来尝试使三个字符串相等。如果没有公共前缀，即三个字符串从第一个字符开始就不相同，那么无法通过剪切任何部分来使它们相等。在这种情况下，返回-1表示不可能只通过剪切操作达到题目要求的状态。
操作次数的计算公式是基于将三个字符串剪切到它们的公共前缀长度来得出的。具体来说，每个字符串需要剪切掉的字符数等于该字符串的总长度减去公共前缀的长度。因此，对所有三个字符串进行操作的总次数等于它们的总长度之和减去三倍的公共前缀长度（因为每个字符串都保留了公共前缀长度的部分）。这个公式简洁地表示了将三个字符串通过剪切变得完全相同所需的最小操作次数。
算法在这种情况下会停止增加公共前缀的长度。循环在检测到任何不匹配（即使是两个字符串相同但第三个不同的情况）时就会中断。这是因为公共前缀必须在所有三个字符串中完全一致。一旦发现不匹配的字符，就意味着公共前缀结束，算法随后会基于已经发现的公共前缀长度来计算操作次数。