题解 | #回文数索引#

题目链接

回文数索引

题目描述

给定一个仅由小写字母组成的字符串。

请找出一个位置（下标从0开始），删掉那个字母之后，字符串变成回文。

题目保证，如果字符串本身不是回文，则总会有一个合法的解。
如果给定的字符串已经是一个回文串，那么输出-1。

解题思路

本题是经典回文判断的变种，最高效的解法是使用双指针。

核心思想

我们使用两个指针，一个从字符串的开头 l 开始，另一个从结尾 r 开始，同时向中间移动并比较对应位置的字符。

寻找不匹配点：
- 当 s[l] 和 s[r] 相等时，说明这对字符符合回文的要求，我们可以继续向内收缩指针（l++, r--）。
- 当第一次遇到 s[l] != s[r] 时，我们就找到了破坏回文对称性的两个字符。
决策与验证：
- 既然 s[l] 和 s[r] 是第一对不匹配的字符，那么为了使整个字符串变为回文，我们必须删除这两个字符中的一个。
- 我们面临两种可能：
  1. 删除 s[l]：如果删除 s[l] 是正确的解，那么剩下的子字符串 s[l+1...r] 必须是一个完美的回文。
  2. 删除 s[r]：如果删除 s[l] 后字符串仍不是回文，那么根据题目的“总会有一个合法的解”的保证，删除 s[r] 必然是正确的解。此时，子字符串 s[l...r-1] 必须是一个回文。
特殊情况：
- 如果双指针的循环正常结束（即 l >= r），这意味着在整个过程中都没有找到不匹配的字符。这说明原字符串本身就是一个回文，按题目要求应返回 -1。

算法步骤总结

初始化指针 l = 0, r = s.length() - 1。
循环比较 s[l] 和 s[r]，当它们相等时，向内移动指针。
如果循环因 l >= r 而结束，返回 -1。
如果循环因 s[l] != s[r] 而中断，我们创建一个辅助函数 is_palindrome(sub_string)。
调用 is_palindrome 检查 s[l+1...r]。如果是回文，返回 l。
否则，直接返回 r。

这个方法只需要对字符串进行一次（最多两次不完整的）遍历，因此效率很高。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 辅助函数，检查子字符串 s[l...r] 是否为回文
bool is_palindrome(const string& s, int l, int r) {
    while (l < r) {
        if (s[l] != s[r]) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

void solve() {
    string s;
    cin >> s;
    int n = s.length();
    int l = 0, r = n - 1;

    // 从两端向中间查找第一个不匹配的字符对
    while (l < r && s[l] == s[r]) {
        l++;
        r--;
    }

    // 如果 l >= r，说明整个字符串都是回文
    if (l >= r) {
        cout << -1 << endl;
        return;
    }

    // 找到第一对不匹配的字符 s[l] 和 s[r]
    // 尝试删除 s[l]，检查 s[l+1...r] 是否为回文
    if (is_palindrome(s, l + 1, r)) {
        cout << l << endl;
    } 
    // 否则，根据题意，删除 s[r] 一定可以构成回文
    else {
        cout << r << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    // 辅助函数，检查子字符串 s 在 [l, r] 区间是否为回文
    private static boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }

    private static void solve(Scanner sc) {
        String s = sc.next();
        int n = s.length();
        int l = 0;
        int r = n - 1;

        // 从两端向中间查找第一个不匹配的字符对
        while (l < r && s.charAt(l) == s.charAt(r)) {
            l++;
            r--;
        }

        // 如果 l >= r，说明整个字符串都是回文
        if (l >= r) {
            System.out.println(-1);
            return;
        }
        
        // 尝试删除 s.charAt(l)，检查剩余部分是否为回文
        if (isPalindrome(s, l + 1, r)) {
            System.out.println(l);
        } 
        // 否则，删除 s.charAt(r)
        else {
            System.out.println(r);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
}

import sys

# 辅助函数，检查子字符串 s[l...r] 是否为回文
def is_palindrome(s, l, r):
    sub = s[l : r + 1]
    return sub == sub[::-1]

def solve():
    s = sys.stdin.readline().strip()
    n = len(s)
    l, r = 0, n - 1
    
    # 从两端向中间查找第一个不匹配的字符对
    while l < r and s[l] == s[r]:
        l += 1
        r -= 1
        
    # 如果 l >= r，说明整个字符串都是回文
    if l >= r:
        print(-1)
        return
        
    # 尝试删除 s[l]，检查剩余部分是否为回文
    if is_palindrome(s, l + 1, r):
        print(l)
    # 否则，删除 s[r]
    else:
        print(r)

def main():
    try:
        t_str = sys.stdin.readline()
        if not t_str:
            return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

算法：双指针
时间复杂度: $\mathcal{O}(N)$ 。在最坏的情况下，我们需要遍历字符串两次（一次找到不匹配点，一次验证子串），其中 N 是字符串的长度。
空间复杂度: $\mathcal{O}(1)$ 。我们只使用了常数个额外的变量来存储指针。