1147.段式回文

链接：1147.段式回文
难度：Hard
标签：贪心、双指针、字符串、动态规划、哈希函数、滚动哈希
简介：给你一个字符串 text，在确保它满足段式回文的前提下，请你返回 段 的 最大数量 k。

题解 1 - typescript

• 编辑时间：2021-12-12
• 执行用时：80ms
• 内存消耗：40.5MB
• 编程语言：typescript
• 解法介绍：dfs 每次读取两头最短相匹配字符数。

function longestDecomposition(text: string): number {
  const n = text.length;
  if (n <= 1) return n;
  let lidx = 1;
  let lstr = text[0];
  let ridx = n - 2;
  let rstr = text[n - 1];
  while (ridx > lidx && lstr !== rstr) {
    lstr += text[lidx++];
    rstr = text[ridx--] + rstr;
  }
  if (ridx <= lidx && lstr !== rstr) return 1;
  return longestDecomposition(text.substring(lidx, ridx + 1)) + 2;
}

题解 2 - cpp

• 编辑时间：2023-04-12
• 执行用时：4ms
• 内存消耗：6MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
public:
    int longestDecomposition(string text) {
        int n = text.size(), res = 0;
        auto check = [&](int i1, int i2, int size) -> bool {
            while (size--) {
                if (text[i1++] != text[i2++]) return false;
            }
            return true;
        };
        for (int i = 0; i <= n / 2; i++) {
            int f = false;
            for (int cnt = 1; i + cnt <= n - i; cnt++) {
                if (check(i, n - i - cnt, cnt)) {
                    f = true;
                    if (i == n - i - cnt) res += 1; // 是一个字符串
                    else res += 2; 
                    i += cnt - 1;
                    break;
                }
            }
            if (!f) {
                if ((n - 2 * i) / 2 != 0) res += 1; // 只剩空字符串
                break;
            }
        }
        return res;
    }
};

题解 3 - python

• 编辑时间：2023-04-12
• 执行用时：44ms
• 内存消耗：14.8MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def longestDecomposition(self, text: str) -> int:
        n = len(text)
        res = 0
        def check(i1: int, i2: int, size: int) -> bool:
            while size:
                if text[i1] != text[i2]:
                    return False
                i1 += 1
                i2 += 1
                size -= 1
            return True
        i = 0
        while i <= n // 2:
            f = False
            cnt = 1
            while i + cnt <= n - i:
                if check(i, n - i - cnt, cnt):
                    f = True
                    if i == n - i - cnt:
                        res += 1
                    else:
                        res += 2
                    i += cnt-1
                    break
                cnt += 1
            if not f:
                if (n - 2 * i) / 2 != 0:
                    res += 1
                break
            i += 1
        return res

题解 4 - rust

• 编辑时间：2023-04-12
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn longest_decomposition(text: String) -> i32 {
        let text = text.chars().collect::<Vec<char>>();
        let n = text.len();
        let mut res = 0;
        let check = |mut i1: usize, mut i2: usize, mut size: usize| -> bool {
            while size != 0 {
                if text[i1] != text[i2] {
                    return false;
                }
                i1 += 1;
                i2 += 1;
                size -= 1;
            }
            true
        };
        let mut i = 0;
        while i <= n / 2 {
            let mut f = false;
            let mut cnt = 1;
            while i + cnt <= n - i {
                if check(i, n - i - cnt, cnt) {
                    f = true;
                    res += if i == n - i - cnt { 1 } else { 2 };
                    i += cnt - 1;
                    break;
                }
                cnt += 1;
            }
            if !f {
                if (n - 2 * i) / 2 != 0 {
                    res += 1;
                }
                break;
            }
            i += 1;
        }
        res
    }
}