解题思路

这是一个回文扩展问题。我们需要找到一个最短的回文，使得给定字符串s可以通过在末尾添加字符来形成回文。关键点如下：

  1. 回文定义：

    • 回文是指从前往后读和从后往后读是一样的字符串。

  2. 最短回文的构造：

    • 我们可以通过找到字符串s的最长回文前缀来确定需要添加的字符。
    • 如果s的前缀是回文的，那么只需在后面添加剩余的字符的反转部分。

  3. 算法步骤：

    • 从字符串的末尾开始，检查每个前缀是否是回文。
    • 找到最长的回文前缀后，计算需要添加的字符数。

代码

#include <iostream>
#include <string>
using namespace std;

class ShortestPalindrome {
public:
    int shortestPalindromeLength(const string& s) {
        int n = s.length();
        if (n == 0) return 0;

        for (int i = 0; i < n; i++) {
            if (isPalindrome(s, i, n - 1)) {
                return n + i;  // 返回最短回文长度
            }
        }
        return n;  // 默认返回n
    }

private:
    bool isPalindrome(const string& s, int left, int right) {
        while (left <= right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};

int main() {
    ShortestPalindrome sp;
    string s;
    cin >> s;
    int result = sp.shortestPalindromeLength(s);
    cout << result << endl;  // 输出最短回文长度
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            if (isPalindrome(s, i, n - 1)) {
                System.out.println(n + i);
                return;
            }
        }
    }

    private static boolean isPalindrome(String s, int left, int right) {
        while (left <= right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

def shortest_palindrome_length(s):
    n = len(s)
    if n == 0:
        return 0

    for i in range(n):
        if is_palindrome(s, i, n - 1):
            return n + i  # 返回最短回文长度
    return n  # 默认返回n

def is_palindrome(s, left, right):
    while left <= right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

# 测试代码
if __name__ == "__main__":
    s = input()
    result = shortest_palindrome_length(s)
    print(result)  # 输出最短回文长度

算法及复杂度

  • 算法：检查回文并计算最短回文长度
  • 时间复杂度：，需要检查每个前缀是否是回文
  • 空间复杂度：，只使用常数额外空间