每日一题非对称之美

题目描述

I-非对称之美_牛客小白月赛31 (nowcoder.com)

题目解析

贪心算法的应用

考虑以下情况：当字符串中的字符全部相同时，即使删除任意一个字符，也无法使其成为一个回文串。这种情况下，我们无法直接套用上述的逐步比较方法。这时，贪心算法就展现了其优势。

算法思路

我们可以利用贪心算法的思想，直接判断最长的回文串。如果整个字符串是回文串，那么我们只需要删除最后一个字符即可得到最长回文串。如果字符串不是回文串，那么我们需要删除的字符数就是字符串的长度。

实现与优化

在实现过程中，我们首先判断字符串是否全部相同，如果是，则直接返回0，因为无论删除哪个字符，剩余字符串都无法成为回文串。然后，我们判断是否为回文串，如果是，则返回字符串长度减一，因为只需要删除一个字符即可。最后，对于其他情况，直接返回字符串长度即可。

代码实现

import java.util.Scanner;

public class Main {
    // 判断是否为回文串
    public static boolean isPalindrome(String str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String str = in.next();
            int n = str.length();
            // 判断是否全部相同
            boolean allSame = true;
            for (int i = 1; i < n; i++) {
                if (str.charAt(i) != str.charAt(0)) {
                    allSame = false;
                    break;
                }
            }
            // 如果全部相同，则无法构成回文串，直接输出0
            if (allSame) {
                System.out.println(0);
                continue;
            }
            // 判断是否为回文串
            if (isPalindrome(str)) {
                System.out.println(n - 1);
            } else {
                System.out.println(n);
            }
        }
    }
}