题解 | #回文数索引#

解题思路

这是一道关于回文串的题目，主要思路如下：

1. 首先判断原字符串是否为回文串，如果是则输出-1
2. 如果不是回文串，则尝试删除每一个位置的字符，判断剩余字符串是否构成回文串
3. 一旦找到一个位置，删除该位置的字符后能构成回文串，则输出该位置索引
4. 判断回文串的方法是从两端向中间比较字符是否相同

代码

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

bool isPalindrome(string& s) {
    int n = s.length();
    for(int i = 0; i < n/2; i++) {
        if(s[i] != s[n-1-i]) return false;
    }
    return true;
}

int main() {
    int T;
    cin >> T;
    while(T--) {
        string s;
        cin >> s;
        
        // 如果已经是回文串
        if(isPalindrome(s)) {
            cout << -1 << endl;
            continue;
        }
        
        // 尝试删除每个位置的字符
        for(int i = 0; i < s.length(); i++) {
            string temp = s.substr(0, i) + s.substr(i+1);
            if(isPalindrome(temp)) {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

import java.util.*;

public class Main {
    static boolean isPalindrome(String s) {
        int n = s.length();
        for(int i = 0; i < n/2; i++) {
            if(s.charAt(i) != s.charAt(n-1-i)) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0) {
            String s = sc.next();
            
            if(isPalindrome(s)) {
                System.out.println(-1);
                continue;
            }
            
            for(int i = 0; i < s.length(); i++) {
                String temp = s.substring(0, i) + s.substring(i+1);
                if(isPalindrome(temp)) {
                    System.out.println(i);
                    break;
                }
            }
        }
    }
}

def is_palindrome(s):
    return all(s[i] == s[len(s)-1-i] for i in range(len(s)//2))

T = int(input())
for _ in range(T):
    s = input()
    
    # 如果已经是回文串
    if is_palindrome(s):
        print(-1)
        continue
    
    # 尝试删除每个位置的字符
    for i in range(len(s)):
        temp = s[:i] + s[i+1:]
        if is_palindrome(temp):
            print(i)
            break

算法及复杂度

• 算法：暴力枚举 + 回文串判断
• 时间复杂度： - 为测试用例数， 为字符串长度
• 空间复杂度： - 需要存储原始字符串和临时字符串