题目描述
你会得到一个字符串 text 。你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk) ，要求满足:
subtexti 是 非空 字符串- 所有子字符串的连接等于
text ( 即subtext1 + subtext2 + ... + subtextk == text )
- 对于所有 i 的有效值( 即
1 <= i <= k ) ，subtexti == subtextk - i + 1 均成立
返回k可能最大值。
示例 1：
输入：text = "ghiabcdefhelloadamhelloabcdefghi"
输出：7
解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。
示例 2：
输入：text = "merchant"
输出：1
解释：我们可以把字符串拆分成 "(merchant)"。
示例 3：
输入：text = "antaprezatepzapreanta"
输出：11
解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a)"。
提示：
1 <= text.length <= 1000text 仅由小写英文字符组成
解法
方法一：贪心 + 双指针
我们可以从字符串的两端开始，寻找长度最短的、相同且不重叠的前后缀：
- 如果找不到这样的前后缀，那么整个字符串作为一个段式回文，答案加 $1$；
- 如果找到了这样的前后缀，那么这个前后缀作为一个段式回文，答案加 $2$，然后继续寻找剩下的字符串的前后缀。
以上贪心策略的证明如下：
假设有一个前后缀 $A_1$ 和 $A_2$ 满足条件，又有一个前后缀 $B_1$ 和 $B_4$ 满足条件，由于 $A_1 = A_2$，且 $B_1=B_4$，那么有 $B_3=B_1=B_4=B_2$，并且 $C_1 = C_2$，因此，如果我们贪心地将 $B_1$ 和 $B_4$ 分割出来，那么剩下的 $C_1$ 和 $C_2$，以及 $B_2$ 和 $B_3$ 也能成功分割。因此我们应该贪心地选择长度最短的相同前后缀进行分割，这样剩余的字符串中，将可能分割出更多的段式回文串。
时间复杂度 $O(n^2)$，空间复杂度 $O(n)$ 或 $O(1)$。其中 $n$ 为字符串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution:
def longestDecomposition(self, text: str) -> int:
ans = 0
i, j = 0, len(text) - 1
while i <= j:
k = 1
ok = False
while i + k - 1 < j - k + 1:
if text[i : i + k] == text[j - k + 1 : j + 1]:
ans += 2
i += k
j -= k
ok = True
break
k += 1
if not ok:
ans += 1
break
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
public int longestDecomposition(String text) {
int ans = 0;
for (int i = 0, j = text.length() - 1; i <= j;) {
boolean ok = false;
for (int k = 1; i + k - 1 < j - k + 1; ++k) {
if (check(text, i, j - k + 1, k)) {
ans += 2;
i += k;
j -= k;
ok = true;
break;
}
}
if (!ok) {
++ans;
break;
}
}
return ans;
}
private boolean check(String s, int i, int j, int k) {
while (k-- > 0) {
if (s.charAt(i++) != s.charAt(j++)) {
return false;
}
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
public:
int longestDecomposition(string text) {
int ans = 0;
auto check = [&](int i, int j, int k) -> bool {
while (k--) {
if (text[i++] != text[j++]) {
return false;
}
}
return true;
};
for (int i = 0, j = text.size() - 1; i <= j;) {
bool ok = false;
for (int k = 1; i + k - 1 < j - k + 1; ++k) {
if (check(i, j - k + 1, k)) {
ans += 2;
i += k;
j -= k;
ok = true;
break;
}
}
if (!ok) {
ans += 1;
break;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | func longestDecomposition(text string) (ans int) {
for i, j := 0, len(text)-1; i <= j; {
ok := false
for k := 1; i+k-1 < j-k+1; k++ {
if text[i:i+k] == text[j-k+1:j+1] {
ans += 2
i += k
j -= k
ok = true
break
}
}
if !ok {
ans++
break
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | function longestDecomposition(text: string): number {
let ans = 0;
for (let i = 0, j = text.length - 1; i <= j; ) {
let ok = false;
for (let k = 1; i + k - 1 < j - k + 1; ++k) {
if (text.slice(i, i + k) === text.slice(j - k + 1, j + 1)) {
ans += 2;
i += k;
j -= k;
ok = true;
break;
}
}
if (!ok) {
++ans;
break;
}
}
return ans;
}
|
方法二：字符串哈希
字符串哈希是把一个任意长度的字符串映射成一个非负整数，并且其冲突的概率几乎为 $0$。字符串哈希用于计算字符串哈希值，快速判断两个字符串是否相等。
因此，在方法一的基础上，我们可以使用字符串哈希的方法，在 $O(1)$ 时间内比较两个字符串是否相等。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | class Solution:
def longestDecomposition(self, text: str) -> int:
def get(l, r):
return (h[r] - h[l - 1] * p[r - l + 1]) % mod
n = len(text)
base = 131
mod = int(1e9) + 7
h = [0] * (n + 10)
p = [1] * (n + 10)
for i, c in enumerate(text):
t = ord(c) - ord('a') + 1
h[i + 1] = (h[i] * base) % mod + t
p[i + 1] = (p[i] * base) % mod
ans = 0
i, j = 0, n - 1
while i <= j:
k = 1
ok = False
while i + k - 1 < j - k + 1:
if get(i + 1, i + k) == get(j - k + 2, j + 1):
ans += 2
i += k
j -= k
ok = True
break
k += 1
if not ok:
ans += 1
break
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 | class Solution {
private long[] h;
private long[] p;
public int longestDecomposition(String text) {
int n = text.length();
int base = 131;
h = new long[n + 10];
p = new long[n + 10];
p[0] = 1;
for (int i = 0; i < n; ++i) {
int t = text.charAt(i) - 'a' + 1;
h[i + 1] = h[i] * base + t;
p[i + 1] = p[i] * base;
}
int ans = 0;
for (int i = 0, j = n - 1; i <= j;) {
boolean ok = false;
for (int k = 1; i + k - 1 < j - k + 1; ++k) {
if (get(i + 1, i + k) == get(j - k + 2, j + 1)) {
ans += 2;
i += k;
j -= k;
ok = true;
break;
}
}
if (!ok) {
++ans;
break;
}
}
return ans;
}
private long get(int i, int j) {
return h[j] - h[i - 1] * p[j - i + 1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 | class Solution {
public:
int longestDecomposition(string text) {
using ull = unsigned long long;
int n = text.size();
int base = 131;
ull p[n + 10];
ull h[n + 10];
p[0] = 1;
h[0] = 0;
for (int i = 0; i < n; ++i) {
int t = text[i] - 'a' + 1;
p[i + 1] = p[i] * base;
h[i + 1] = h[i] * base + t;
}
int ans = 0;
auto get = [&](int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
};
for (int i = 0, j = n - 1; i <= j;) {
bool ok = false;
for (int k = 1; i + k - 1 < j - k + 1; ++k) {
if (get(i + 1, i + k) == get(j - k + 2, j + 1)) {
ans += 2;
i += k;
j -= k;
ok = true;
break;
}
}
if (!ok) {
++ans;
break;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | func longestDecomposition(text string) (ans int) {
n := len(text)
base := 131
h := make([]int, n+10)
p := make([]int, n+10)
p[0] = 1
for i, c := range text {
t := int(c-'a') + 1
p[i+1] = p[i] * base
h[i+1] = h[i]*base + t
}
get := func(l, r int) int {
return h[r] - h[l-1]*p[r-l+1]
}
for i, j := 0, n-1; i <= j; {
ok := false
for k := 1; i+k-1 < j-k+1; k++ {
if get(i+1, i+k) == get(j-k+2, j+1) {
ans += 2
i += k
j -= k
ok = true
break
}
}
if !ok {
ans++
break
}
}
return
}
|