题目描述
解法
方法一：双指针
我们记录字符串 \(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;
};
|