class Solution {
public:
int longestDecomposition(string text) {
}
};
1147. 段式回文
你会得到一个字符串 text 。你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk) ，要求满足:
subtexti 是非空字符串text ( 即subtext1 + subtext2 + ... + subtextk == text )subtexti == subtextk - i + 1 表示所有 i 的有效值( 即 1 <= i <= k )返回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)(tpe)(za)(pre)(a)(nt)(a)"。
示例 4：
输入：text = "aaa" 输出：3 解释：我们可以把字符串拆分成 "(a)(a)(a)"。
提示：
1 <= text.length <= 1000text 仅由小写英文字符组成原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2023-04-12 09:30:04
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
}
java 解法, 执行用时: 1 ms, 内存消耗: 39.7 MB, 提交时间: 2023-04-12 09:29:49
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];
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 15.1 MB, 提交时间: 2023-04-12 09:29:22
'''
字符串哈希
字符串哈希是把一个任意长度的字符串映射成一个非负整数，并且其冲突的概率几乎为 0。
字符串哈希用于计算字符串哈希值，快速判断两个字符串是否相等。
'''
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
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-04-12 09:28:29
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
}
java 解法, 执行用时: 0 ms, 内存消耗: 39.6 MB, 提交时间: 2023-04-12 09:28:11
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;
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 14.8 MB, 提交时间: 2023-04-12 09:26:41
'''
贪心 + 双指针
我们可以从字符串的两端开始，寻找长度最短的、相同且不重叠的前后缀：
如果找不到这样的前后缀，那么整个字符串作为一个段式回文，答案加 1；
如果找到了这样的前后缀，那么这个前后缀作为一个段式回文，答案加 2，
然后继续寻找剩下的字符串的前后缀。
'''
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