给定字符串的可能回文检查 - 需要高效代码

Question

我正在解决 Palindrome index 问题。问题的难度级别很简单，但我仍然没有通过所有测试用例:(。在大多数测试用例中，我超时了，令人惊讶的是，一个测试用例也失败了。我在谷歌上搜索了回文检查——似乎只有两种方法——

1. Using StringBuilder reverse() method.
2. Comparing characters till mid of the string length.

我尝试了两种方法，但仍然没有成功。

以下是我的尝试：

import java.util.Scanner;

public class PalindromeIndex {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int totalTestCases = Integer.parseInt(scanner.nextLine());

        String testString = null;
        StringBuffer outputString = new StringBuffer();
        for (int i = 0; i < totalTestCases; i++) {
            testString = scanner.nextLine();
            boolean is0thElementTrue = false;
            // One lettered word is always a palindrome so checked that
            // condition
            if (isPalindrome(testString) || testString.length() == 1) {
                outputString.append("-1");
            } else {
                if (isPalindrome(testString.substring(1))) {
                    outputString.append("0 ");
                    is0thElementTrue = true;
                }
                // See here j - index starts from 1 as initial case is
                // already
                // handled in above if-condition
                // Also see the condition checks [j < testString.length() -
                // 1;]
                // because (testString.length() - 1) is checked separately
                // after
                // this for loop.;
                boolean isLoopSuccessAtleastOnce = false;
                for (int j = 1; j < testString.length() - 1; j++) {
                    if (isPalindrome(testString.substring(0, j)
                            + testString.substring(j + 1, testString.length()))) {
                        isLoopSuccessAtleastOnce = true;
                        if (is0thElementTrue) {
                            outputString.append(j);
                            is0thElementTrue = false;
                        } else
                            outputString.append(" " + j);
                    }
                }
                if (isPalindrome(testString.substring(0,
                        testString.length() - 1))) {
                    if (isLoopSuccessAtleastOnce)
                        outputString.append(" " + (testString.length() - 1));
                    else
                        outputString.append((testString.length() - 1));
                }
            }
            outputString.append("\n");
        }
        System.out.println(outputString.toString());
        scanner.close();
    }

    private static boolean isPalindrome(String str) {
        StringBuilder strBuffer = new StringBuilder(str);
        return str.equalsIgnoreCase(strBuffer.reverse().toString());
    }

    private static boolean isPalindrome_2ndWay(String str) {
        int n = str.length();
        for (int i = 0; i < (n / 2) + 1; ++i) {
            if (str.charAt(i) != str.charAt(n - i - 1)) {
                return false;
            }
        }

        return true;
    }
}

Answer 1

这就是我的答案：

String text = "Anita lava la tina";
text = text.toLowerCase().replaceAll(" ", "");

StringBuilder strb = new StringBuilder(text);

String text2 = strb.reverse().toString();

System.out.println("Palindrome: " + text.equals(text2));

Answer 2

您的解决方案是二次方的，这绝对不是该网站正在寻找的，您可以做得更好。

考虑一下。如果第一个和最后一个字符彼此不相等，那么其中一个就是答案。如果它们相等，则可以将相同的逻辑应用于第二个和最后一个字符的前一个。等等

Answer 3

尝试更有效的解决方案：使用 StringBuilder.deleteCharAt(int index) 但请注意，您要么必须将其放回原位，要么从要测试的字符串中创建一个新的 StringBuilder。然后您可以迭代字符，删除它们并使用现有方法测试生成的字符串。

小记：

Note: If the character at the given index is a supplementary character, this method does not remove the entire character.

...但我不认为这是在此时测试您的 Unicode 知识。

Answer 4

问题描述为

figure out the index of the character on whose removal will make the string a palindrome. There will always be a valid solution. In case string is already palindrome, then -1 is also a valid answer

所以可以这样处理：

找到使字符串不是回文的第一个字符，换句话说，第一个与 "mirror" 位置的字符不同的字符。
如果没有这个字符，则字符串已经是回文
如果有这样的字符，判断去掉它是否使字符串成为回文。如果是，则您已找到解决方案。如果不是，那么镜像位置的字符一定是答案（问题说明总是有一个有效的解决方案）。

找到使字符串不是回文的第一个字符是 O(n)。这个操作每个字符串最多会执行两次，所以全局解还是O(n).

这是一个可能的实现。它已通过所有测试

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class PalindromeIndex {

    public static void main(String[] args) {

        List<String> inputStrs = readInput();

        for (String inputStr : inputStrs) {
            int index = findIndexToRemove(inputStr);
            System.out.println(index);
        }
    }

    private static List<String> readInput() {
        int inputSize;
        List<String> inputStrs = new ArrayList<>();
        try(Scanner scanner = new Scanner(System.in)){
            inputSize = Integer.parseInt(scanner.nextLine());
            for (int i = 0; i < inputSize; i++) {
                inputStrs.add(scanner.nextLine());
            }
        }
        return inputStrs;
    }

    private static int findIndexToRemove(String inputStr){
        int i = findIndexOfDifference(inputStr);
        int result;
        if(i == -1){
            // String is a palindrome
            result = -1;
        } else {
            // Either the char at i or the char at the opposite side (length-1-i)
            // is the char to remove. Let's remove one of them and see
            // if the result is a palindrome
            if(findIndexOfDifference(removeChar(inputStr, i)) == -1){
                result = i;
            } else {
                result = inputStr.length() - 1 - i;
            }
        }
        return result;
    }

    /**
     * Returns the position of the first character that is not equal to the
     * character at its simmetric position (i.e. the char at the same position
     * counting from the opposite side of the string).
     */
    private static int findIndexOfDifference(String inputStr){
        int i=0, j=inputStr.length()-1;
        while(i<j && inputStr.charAt(i) == inputStr.charAt(j)){
            i++;
            j--;
        }
        int index;
        if(i<j){
            index = i;
        } else {
            index = -1;
        }
        return index;
    }

    private static String removeChar(String str, int charIndex){
        String firstPart = str.substring(0, charIndex);
        String secondPart = str.substring(Math.min(str.length(), charIndex+1), str.length());
        return firstPart + secondPart;
    }

}

给定字符串的可能回文检查 - 需要高效代码

Possible Palindrome check from given string - efficient code needed

java

optimization

performance

palindrome