替代嵌套循環以提高代碼的性能？

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個字母。