Альтернатива вложенным петлям для повышения производительности кода?

Question

Я сделал небольшую программу, которая проверяет, какой индекс нужно удалить, чтобы сделать его палиндромом. Поскольку в одном выполнении может быть много тестовых случаев, я вынужден использовать глубокое вложение для циклов. Я хочу знать, есть ли альтернативный способ петли вложенности для повышения производительности.

Ниже мой код:

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] 

Последние 3 Параметры findPalindromes() используются для сбора результатов. Если вы хотите собрать индексы символов палиндрома, вы можете изменить это.

Если вы хотите, чтобы индексы символов были удалены, я бы посоветовал вам собирать индексы символов палиндрома, то есть индексы для сохранения, а затем инвертировать результаты в индексы для удаления после возврата findPalindromes().

Обратите внимание, что хотя этот алгоритм проще вашего, он может быть не быстрее, если вам нужен самый длинный палиндром, потому что вам нужно искать все потенциальные палиндромы. Обратите внимание, что у 3-го тестового примера есть палиндром, используя первые 3 буквы abcba, но самые длинные палиндромы не используют все первые три буквы.