跳转至

3460. 最多删除一次后的最长公共前缀 🔒

题目描述

给定两个字符串 s 和 t。

返回从 s 最多 删除一个字母后，s 和 t 的 最长公共 前缀 的 长度。

注意：可以保留 s 而不做任何删除。

 

示例 1：

输入：s = "madxa", t = "madam"

输出：4

解释：

从 s 删除 s[3] 得到 "mada"，与 t 的最长公共前缀长度为 4。

示例 2：

输入：s = "leetcode", t = "eetcode"

输出：7

解释：

从 s 删除 s[0] 得到 "eetcode"，与 t 匹配。

示例 3：

输入：s = "one", t = "one"

输出：3

解释：

不需要删除。

示例 4：

输入：s = "a", t = "b"

输出：0

解释：

s 和 t 不可能有公共前缀。

 

提示：

  • 1 <= s.length <= 105
  • 1 <= t.length <= 105
  • s 和 t 只包含小写英文字母。

解法

方法一：双指针

我们记录字符串 \(s\) 和 \(t\) 的长度分别为 \(n\) 和 \(m\)，然后用两个指针 \(i\) 和 \(j\) 分别指向字符串 \(s\) 和 \(t\) 的开头，用一个布尔变量 \(\textit{rem}\) 记录是否已经删除过字符。

接下来，我们开始遍历字符串 \(s\) 和 \(t\)，如果 \(s[i]\) 不等于 \(t[j]\)，我们就判断是否已经删除过字符，如果已经删除过字符，我们就退出循环，否则我们标记已经删除过字符，然后跳过 \(s[i]\)；否则，我们跳过 \(s[i]\) 和 \(t[j]\)。继续遍历，直到 \(i \geq n\) 或 \(j \geq m\)。

最后返回 \(j\) 即可。

时间复杂度 \(O(n+m)\)，其中 \(n\) 和 \(m\) 分别是字符串 \(s\) 和 \(t\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def longestCommonPrefix(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        i = j = 0
        rem = False
        while i < n and j < m:
            if s[i] != t[j]:
                if rem:
                    break
                rem = True
            else:
                j += 1
            i += 1
        return j

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int longestCommonPrefix(String s, String t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        boolean rem = false;
        while (i < n && j < m) {
            if (s.charAt(i) != t.charAt(j)) {
                if (rem) {
                    break;
                }
                rem = true;
            } else {
                ++j;
            }
            ++i;
        }
        return j;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestCommonPrefix(string s, string t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        bool rem = false;
        while (i < n && j < m) {
            if (s[i] != t[j]) {
                if (rem) {
                    break;
                }
                rem = true;
            } else {
                ++j;
            }
            ++i;
        }
        return j;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func longestCommonPrefix(s string, t string) int {
    n, m := len(s), len(t)
    i, j := 0, 0
    rem := false
    for i < n && j < m {
        if s[i] != t[j] {
            if rem {
                break
            }
            rem = true
        } else {
            j++
        }
        i++
    }
    return j
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function longestCommonPrefix(s: string, t: string): number {
    const [n, m] = [s.length, t.length];
    let [i, j] = [0, 0];
    let rem: boolean = false;
    while (i < n && j < m) {
        if (s[i] !== t[j]) {
            if (rem) {
                break;
            }
            rem = true;
        } else {
            ++j;
        }
        ++i;
    }
    return j;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
impl Solution {
    pub fn longest_common_prefix(s: String, t: String) -> i32 {
        let (n, m) = (s.len(), t.len());
        let (mut i, mut j) = (0, 0);
        let mut rem = false;

        while i < n && j < m {
            if s.as_bytes()[i] != t.as_bytes()[j] {
                if rem {
                    break;
                }
                rem = true;
            } else {
                j += 1;
            }
            i += 1;
        }

        j as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var longestCommonPrefix = function (s, t) {
    const [n, m] = [s.length, t.length];
    let [i, j] = [0, 0];
    let rem = false;
    while (i < n && j < m) {
        if (s[i] !== t[j]) {
            if (rem) {
                break;
            }
            rem = true;
        } else {
            ++j;
        }
        ++i;
    }
    return j;
};

评论