Epic | OAMaster

01Palindrome Word

A palindrome is a sequence that reads the same forwards as it does backwards. "abba", for e

Example 1

Input:

s = "abcdefccfed"

Output:

cdefc
fccf
ccf

Explanation: The function prints all palindromes of 3 or more characters in length contained in the string "abcdefccfed", which are case-sensitive. The palindromes "cdefc", "fccf", and "ccf" are found and printed, while others like "cac", "fcf", or "cfcfc" are not printed due to case-sensitivity.

解法

中心扩展法找所有长度 ≥ 3 的回文子串：对每个位置同时尝试奇数中心 (i,i) 和偶数中心 (i,i+1)，向外扩展并打印每个有效回文。注意大小写敏感。时间 O(n²)，空间 O(1)(不算输出)。

from typing import List

def printAllPalindromes(s: str) -> List[str]:
    result: List[str] = []
    n = len(s)
    def expand(left: int, right: int) -> None:
        while left >= 0 and right < n and s[left] == s[right]:
            if right - left + 1 >= 3:
                result.append(s[left:right + 1])
            left -= 1
            right += 1
    for i in range(n):
        expand(i, i)
        expand(i, i + 1)
    return result

import java.util.*;

class Solution {
    List<String> printAllPalindromes(String s) {
        List<String> result = new ArrayList<>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            expand(s, i, i, result);
            expand(s, i, i + 1, result);
        }
        return result;
    }
    private void expand(String s, int l, int r, List<String> result) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            if (r - l + 1 >= 3) result.add(s.substring(l, r + 1));
            l--; r++;
        }
    }
}

#include <vector>
#include <string>

class Solution {
public:
    std::vector<std::string> printAllPalindromes(std::string s) {
        std::vector<std::string> result;
        int n = s.size();
        auto expand = [&](int l, int r) {
            while (l >= 0 && r < n && s[l] == s[r]) {
                if (r - l + 1 >= 3) result.push_back(s.substr(l, r - l + 1));
                l--; r++;
            }
        };
        for (int i = 0; i < n; i++) {
            expand(i, i);
            expand(i, i + 1);
        }
        return result;
    }
};