替代嵌套循环以提高代码的性能？

Question

我做了一个小程序，它检查哪些索引需要删除才能成为回文。由于在一次执行中可能会有很多测试用例，我不得不使用for循环的深层嵌套。我想知道是否有任何替代方法来嵌套循环以提高性能。

以下是我的代码：

import java.util.*; 
import java.io.*; 
public class Testhis { 
public static void main(String[] args) throws Exception { 
     Scanner sc=new Scanner(System.in); 
    //System.out.println("No. of testcases:"); 
    int testcases=sc.nextInt(); 
    String strin[]=new String[testcases]; 

    for (int i=0;i<testcases;i++) 
      strin[i]=sc.next(); 
    int res[]= checkPalindromeIndex(strin); 
    for(int i=0;i<res.length;i++) 
     System.out.println(res[i]); 
    } 

    private static int[] checkPalindromeIndex(String[] strin) { 
     int result[]=new int[strin.length]; 
     a: 
     for(int i=0;i<strin.length;i++){ 
     System.out.println("checking:::::"+strin[i]); 
     if(checkPalFlag(strin[i])){ 
      result[i]=-1; 
      continue a; 
     } 
     else{ 

      for(int j=0;j<strin[i].length();j++){ 
       StringBuilder sb=new StringBuilder(strin[i]); 
       String teststr=sb.deleteCharAt(j).toString(); 
       System.out.println("resulting string:"+teststr); 
       if(checkPalFlag(teststr)){ 
        result[i]=j; 
        continue a; 
       } 
      } 

    } 


} 
    return result; 
} 

private static boolean checkPalFlag(String string) { 
    boolean flag=false;int len=string.length(); 
    for(int i=0;i<(len+1)/2;i++){ 
     if(string.charAt(i)==string.charAt(len-(i+1))){ 
      flag=true; 
      continue; 
     } 
     else{ 
      flag=false; 
      break; 
     } 
    } 
    System.out.println("string "+string+" is a palindrome? :"+flag); 
    return flag; 
} 

} 

Answer 1

下面的代码将返回文本的所有回文。

private static String[] findAllPalindromesInText(String text) { 
    // Eliminate all non-letter/digit from text 
    String normalized = text.toLowerCase(Locale.ROOT).replaceAll("[^\\p{Ll}\\p{N}]", ""); 
    // Collect all palindromes 
    Set<String> allPalindromes = new HashSet<>(); 
    findPalindromes(normalized, 0, normalized.length() - 1, "", "", allPalindromes); 
    // Sort palindromes 
    String[] result = allPalindromes.toArray(new String[allPalindromes.size()]); 
    Arrays.sort(result, (s1, s2) -> { 
     int cmp = Integer.compare(s2.length(), s1.length()); // sort longest first 
     if (cmp == 0) 
      cmp = s1.compareTo(s2); // sort by text 
     return cmp; 
    }); 
    return result; 
} 
private static void findPalindromes(String text, int first, int last, 
            String prefix, String suffix, Set<String> allPalindromes) { 
    for (int i = first; i <= last; i++) { 
     char ch = text.charAt(i); 
     allPalindromes.add(prefix + ch + suffix); 
     for (int j = last; j > i; j--) 
      if (text.charAt(j) == ch) { 
       allPalindromes.add(prefix + ch + ch + suffix); 
       findPalindromes(text, i + 1, j - 1, prefix + ch, ch + suffix, allPalindromes); 
      } 
    } 
} 

测试结果

// for input "abcb" 
[bcb, bb, a, b, c] 

// for input "alibaba" 
[ababa, abba, aaa, aba, aia, ala, bab, aa, bb, a, b, i, l] 

// for input "abcdabdcabc" 
[acdadca, acdbdca, bcdadcb, bcdbdcb, acddca, bcddcb, ababa, abcba, abdba, acaca, acbca, acdca, adada, adbda, babab, bacab, badab, bcacb, bcbcb, bcdcb, bdadb, bdbdb, cabac, cacac, cadac, cbabc, cbcbc, cbdbc, cdadc, cdbdc, abba, acca, adda, baab, bccb, bddb, caac, cbbc, cddc, aaa, aba, aca, ada, bab, bbb, bcb, bdb, cac, cbc, ccc, cdc, dad, dbd, aa, bb, cc, dd, a, b, c, d] 

的findPalindromes()最后3个参数用来收集结果。如果您想收集回文字符的索引，则可以更改为执行此操作。

如果要删除字符索引，我建议您收集回文字符的索引，即索引保留，然后在findPalindromes()返回后，将结果反转为要索引的索引。

请注意，虽然此算法比您的算法更简单，但如果您想要最长的回文序列，速度可能会更快，因为您必须搜索所有潜在回文。请注意，第3个测试用例的回文序列使用前3个字母abcba，但最长的回文不使用前3个字母。