How do I approach the 'Make Three Strings Equal' problem?

Start by calculating the longest common prefix for the three strings. Then, determine how many characters need to be removed from each string to make them equal.

What happens if there is no common prefix?

If no common prefix exists, it's impossible to make the strings equal, and the answer should be -1.

Is it necessary to delete characters from the end of the strings?

Yes, the problem specifically requires you to delete characters from the rightmost end of the strings to make them equal.

What is the time complexity of this problem?

The time complexity is O(n), where n is the length of the longest string, due to the need to find the longest common prefix and calculate the deletions.

Can this problem be solved if we have more than three strings?

Yes, you can extend the solution to handle more than three strings by calculating the longest common prefix among all the strings and then applying the same deletion strategy.

#2937

Easy

auto_awesomeString-driven solution strategy

LeetCode 题解工作台

使三个字符串相等

给你三个字符串 s1 、 s2 和 s3 。你可以根据需要对这三个字符串执行以下操作任意次数。在每次操作中，你可以选择其中一个长度至少为 2 的字符串并删除其最右位置上的字符。如果存在某种方法能够使这三个字符串相等，请返回使它们相等所需的最小操作次数；否则，返回 -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 。

提示：

1 <= s1.length, s2.length, s3.length <= 100
s1、s2 和 s3 仅由小写英文字母组成。

lightbulb

解题思路

方法一：枚举

根据题目描述，我们知道，如果删除字符后的三个字符串相等，那么它们存在一个长度大于 $1$ 的公共前缀。因此，我们可以枚举公共前缀的位置 $i$ ，如果当前下标 $i$ 对应的三个字符不完全相等，那么公共前缀长度为 $i$ ，此时，我们判断 $i$ 是否为 $0$ ，若是，返回 $-1$ ，否则返回 $s - 3 \times i$ ，其中 $s$ 为三个字符串的长度和。

时间复杂度 $O(n)$ ，其中 $n$ 为三个字符串的最小长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def findMinimumOperations(self, s1: str, s2: str, s3: str) -> int:
        s = len(s1) + len(s2) + len(s3)
        n = min(len(s1), len(s2), len(s3))
        for i in range(n):
            if not s1[i] == s2[i] == s3[i]:
                return -1 if i == 0 else s - 3 * i
        return s - 3 * n

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a solution that efficiently calculates the longest common prefix of the three strings.
question_mark
Evaluate if the candidate handles edge cases, such as strings that cannot be made equal.
question_mark
Consider how the candidate approaches calculating the necessary deletions and the final result.

warning

常见陷阱

外企场景

error
Overcomplicating the solution with unnecessary operations or nested loops.
error
Failing to account for edge cases, such as strings with no common prefix.
error
Not optimizing for time complexity, especially when dealing with strings of varying lengths.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The problem can be extended to handle more than three strings.
arrow_right_alt
A variant could involve restricting the number of deletions per string.
arrow_right_alt
Another variant might require making the strings equal by removing characters from both ends instead of just the right side.

help

常见问题

外企场景

继续练习

#2938 区分黑球与白球 #2933 高访问员工 #2942 查找包含给定字符的单词