Leetcode 第 372 场周赛题解

Leetcode 第 372 场周赛题解

题目1：2937. 使三个字符串相等

思路

枚举。

设 len1、len2、len3 分别为字符串 s1、s2、s3 的长度。

min_len 是 3 个字符串长度的最小值。

枚举 len = min_len 到 len = 1，设 t1、t2、t3 分别是字符串 s1、s2、s3 的从 0 开始、长度为 len 的子串。

如果 t1 == t2 == t3，说明可以通过操作（选择其中一个长度至少为 2 的字符串并删除其最右位置上的字符）使这三个字符串相等，最小操作次数 = len1 + len2 + len3 - 3 * len。

否则，返回 -1。

代码

/*
 * @lc app=leetcode.cn id=2937 lang=cpp
 *
 * [2937] 使三个字符串相等
 */

// @lc code=start
class Solution
{
public:
    int findMinimumOperations(string s1, string s2, string s3)
    {
        int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
        int min_len = min(len1, min(len2, len3));
        for (int len = min_len; len >= 1; len--)
        {
            string t1 = s1.substr(0, len), t2 = s2.substr(0, len), t3 = s3.substr(0, len);
            if (t1 == t2 && t2 == t3)
                return len1 + len2 + len3 - 3 * len;
        }
        return -1;
    }
};
// @lc code=end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复杂度分析

时间复杂度：O(min_len)，其中 min_len 为三个字符串中的最短字符串的长度。

空间复杂度：O(1)。

题目2：

思路

代码

在这里插入代码片
1

复杂度分析

时间复杂度：O()。

空间复杂度：O()。

题目3：

思路

代码

在这里插入代码片
1

复杂度分析

时间复杂度：O()。

空间复杂度：O()。

题目4：

思路

代码

在这里插入代码片
1

复杂度分析

时间复杂度：O()。

空间复杂度：O()。