代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你三个字符串 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
仅由小写英文字母组成。根据题目描述,我们知道,如果删除字符后的三个字符串相等,那么它们存在一个长度大于 $1$ 的公共前缀。因此,我们可以枚举公共前缀的位置 $i$,如果当前下标 $i$ 对应的三个字符不完全相等,那么公共前缀长度为 $i$,此时,我们判断 $i$ 是否为 $0$,若是,返回 $-1$,否则返回 $s - 3 \times i$,其中 $s$ 为三个字符串的长度和。
时间复杂度 $O(n)$,其中 $n$ 为三个字符串的最小长度。空间复杂度 $O(1)$。
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
class Solution {
public int findMinimumOperations(String s1, String s2, String s3) {
int s = s1.length() + s2.length() + s3.length();
int n = Math.min(Math.min(s1.length(), s2.length()), s3.length());
for (int i = 0; i < n; ++i) {
if (!(s1.charAt(i) == s2.charAt(i) && s2.charAt(i) == s3.charAt(i))) {
return i == 0 ? -1 : s - 3 * i;
}
}
return s - 3 * n;
}
}
class Solution {
public:
int findMinimumOperations(string s1, string s2, string s3) {
int s = s1.size() + s2.size() + s3.size();
int n = min({s1.size(), s2.size(), s3.size()});
for (int i = 0; i < n; ++i) {
if (!(s1[i] == s2[i] && s2[i] == s3[i])) {
return i == 0 ? -1 : s - 3 * i;
}
}
return s - 3 * n;
}
};
func findMinimumOperations(s1 string, s2 string, s3 string) int {
s := len(s1) + len(s2) + len(s3)
n := min(len(s1), len(s2), len(s3))
for i := range s1[:n] {
if !(s1[i] == s2[i] && s2[i] == s3[i]) {
if i == 0 {
return -1
}
return s - 3*i
}
}
return s - 3*n
}
function findMinimumOperations(s1: string, s2: string, s3: string): number {
const s = s1.length + s2.length + s3.length;
const n = Math.min(s1.length, s2.length, s3.length);
for (let i = 0; i < n; ++i) {
if (!(s1[i] === s2[i] && s2[i] === s3[i])) {
return i === 0 ? -1 : s - 3 * i;
}
}
return s - 3 * n;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。