使三个字符串相等

难度:

标签:

题目描述

You are given three strings: s1, s2, and s3. In one operation you can choose one of these strings and delete its rightmost character. Note that you cannot completely empty a string.

Return the minimum number of operations required to make the strings equal. If it is impossible to make them equal, return -1.

Example 1:

Input: s1 = "abc", s2 = "abb", s3 = "ab"

Output: 2

Explanation: Deleting the rightmost character from both s1 and s2 will result in three equal strings.

Example 2:

Input: s1 = "dac", s2 = "bac", s3 = "cac"

Output: -1

Explanation: Since the first letters of s1 and s2 differ, they cannot be made equal.

Constraints:

1 <= s1.length, s2.length, s3.length <= 100
s1, s2 and s3 consist only of lowercase English letters.

代码结果

运行时间: 27 ms, 内存: 16.1 MB

// 思路：使用Java Stream来处理公共后缀的查找和删除操作次数的计算。
// 主要思路与普通Java版本一致，只是通过流的方式进行数据处理。

import java.util.stream.IntStream;

public class SolutionStream {
    public int minOperations(String s1, String s2, String s3) {
        int minLength = IntStream.of(s1.length(), s2.length(), s3.length()).min().orElse(0);

        long commonSuffixLength = IntStream.range(0, minLength)
            .mapToObj(i -> new int[]{s1.charAt(s1.length() - 1 - i), s2.charAt(s2.length() - 1 - i), s3.charAt(s3.length() - 1 - i)})
            .takeWhile(chars -> chars[0] == chars[1] && chars[1] == chars[2])
            .count();

        int totalRemovals = (s1.length() - (int) commonSuffixLength) +
                            (s2.length() - (int) commonSuffixLength) +
                            (s3.length() - (int) commonSuffixLength);

        return totalRemovals == 0 ? -1 : totalRemovals;
    }
}

解释

方法:

此题解通过检查三个字符串s1, s2, s3的公共前缀来解决问题。首先，通过一个循环比较所有字符串在同一位置的字符是否相同，如果相同，则继续检查下一个字符；如果不同，或任一字符串的长度被耗尽，则停止循环。循环结束后，如果存在公共前缀（即i>0），则计算将三个字符串剪切到公共前缀长度所需的操作次数，这等于三个字符串的总长度减去三倍的公共前缀长度。如果没有公共前缀（i == 0），则直接返回-1，表示无法通过剪切使三个字符串相等。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

在题解中，你是如何处理每个字符串长度不等但可能存在公共前缀的情况？

▷

在题解中，通过使用`min(len(s1), len(s2), len(s3))`作为循环的终止条件，确保了比较过程不会超出任何一个字符串的长度。这意味着在每个字符串的共同长度范围内检查字符是否相等。一旦达到任何一个字符串的结束或者发现不匹配的字符，循环就会停止。这种方法确保了算法处理不同长度字符串的能力，只关注可能的最长公共前缀。

🦆

为什么当公共前缀长度为0时直接返回-1，而不考虑其他可能的操作来使三个字符串相等？

▷

题解中当公共前缀长度为0时返回-1，是基于题目的设定，即只通过剪切字符串的操作来尝试使三个字符串相等。如果没有公共前缀，即三个字符串从第一个字符开始就不相同，那么无法通过剪切任何部分来使它们相等。在这种情况下，返回-1表示不可能只通过剪切操作达到题目要求的状态。

🦆

题解中提到的操作次数计算公式是怎么得出的，能详细解释一下吗？

▷

操作次数的计算公式是基于将三个字符串剪切到它们的公共前缀长度来得出的。具体来说，每个字符串需要剪切掉的字符数等于该字符串的总长度减去公共前缀的长度。因此，对所有三个字符串进行操作的总次数等于它们的总长度之和减去三倍的公共前缀长度（因为每个字符串都保留了公共前缀长度的部分）。这个公式简洁地表示了将三个字符串通过剪切变得完全相同所需的最小操作次数。

🦆

如果在某一步中，两个字符串的字符相同，但第三个字符串的字符不同，这种情况下算法如何处理？

▷

算法在这种情况下会停止增加公共前缀的长度。循环在检测到任何不匹配（即使是两个字符串相同但第三个不同的情况）时就会中断。这是因为公共前缀必须在所有三个字符串中完全一致。一旦发现不匹配的字符，就意味着公共前缀结束，算法随后会基于已经发现的公共前缀长度来计算操作次数。

使三个字符串相等

题目描述

代码结果

解释

代码细节讲解

相关问题