leetcode-No.2937.使三个字符串相等

题目

给你三个字符串 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 。

答案

"""
给你三个字符串 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 。
"""


class Solution(object):
    def findMinimumOperations(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: int
        """
        count = 0
        for x, y, z in zip(s1, s2, s3):
            if x != y or x != z:
                break
            count += 1
        if count == 0:
            return -1
        else:
            return len(s1) + len(s2) + len(s3) - count * 3


if __name__ == '__main__':
    s1 = "dac"
    s2 = "bac"
    s3 = "cac"
    sol = Solution()
    print(sol.findMinimumOperations(s1, s2, s3))

if __name__ == '__main__':
    s1 = "abc"
    s2 = "abb"
    s3 = "ab"
    sol = Solution()
    print(sol.findMinimumOperations(s1, s2, s3))

结果分析

这段代码的时间复杂度和空间复杂度都为O(n)，其中n 是字符串 s1、s2 和 s3 的长度之和，因为在这段代码中，我们使用了一个循环，其迭代次数与输入的字符串长度成正比。此外，我们只需要常数级别的额外空间来存储变量，因此空间复杂度为O(1)