解题思路

这是一个字符串处理问题，需要在字符串末尾添加最少的字符使其成为回文串。

关键点：

  1. 从左到右遍历字符串的每个位置
  2. 判断从位置 到末尾的子串是否为回文串
  3. 如果找到回文子串，则将位置 之前的子串反转后作为结果

算法步骤：

  1. 遍历字符串的每个位置 （从 到 ）
  2. 获取从位置 到末尾的子串
  3. 判断该子串是否为回文串
  4. 如果是回文串，则返回位置 之前的子串的反转

代码

class Palindrome {
public:
    string addToPalindrome(string A, int n) {
        for (int i = 1; i < n; i++) {
            string suffix = A.substr(i);
            string reversed = suffix;
            reverse(reversed.begin(), reversed.end());
            
            if (suffix == reversed) {
                string prefix = A.substr(0, i);
                reverse(prefix.begin(), prefix.end());
                return prefix;
            }
        }
        return A;
    }
};

import java.util.*;

public class Palindrome {
    public String addToPalindrome(String A, int n) {
        for (int i = 1; i < n; i++) {
            String suffix = A.substring(i, n);
            if (suffix.equals(new StringBuffer(suffix).reverse().toString())) {
                return new StringBuffer(A.substring(0, i)).reverse().toString();
            }
        }
        return A;
    }
}

class Palindrome:
    def addToPalindrome(self, A, n):
        for i in range(1, n):
            suffix = A[i:]
            if suffix == suffix[::-1]:
                return A[:i][::-1]
        return A

算法及复杂度

  • 算法：字符串处理 + 回文判断
  • 时间复杂度：，其中 是字符串长度
  • 空间复杂度：，用于存储子串