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

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

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

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

Answer 2

这将是我的答案：

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 3

尝试更有效的解决方案：使用StringBuilder.deleteCharAt(int index)但要注意，您必须将其放回或从要创建的字符串中新建StringBuilder以进行测试。然后你可以遍历字符，删除它们并使用你现有的方法测试结果字符串。

小记：

注：如果给定索引处的字符是增补字符，这种方法并不能删除整个字符。

...但我不认为这是测试你的Unicode知识在这一点上。

Answer 4

的问题表述为

弄清楚其上去除将使串回文字符的索引。总会有一个有效的解决方案。如果字符串已回文，然后-1也是一个有效的答案

因此，它可以如下走近：

• 找到的第一个字符，使字符串不是回文，换句话说，第一个字符与“镜像”位置上的字符不同。
• 如果没有这样的字符，字符串已经是回文。
• 如果有这样的字符，找出是否删除它使字符串回文。如果是这样，你已经找到了解决方案。如果没有，那么镜子位置上的角色必须是答案（问题指出总是有一个有效的解决方案）。

查找使字符串不是回文的第一个字符是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; 
    } 

}