Wie finde ich die Länge der Teilkette eines Palindroms, das selbst kein Palindrom ist?

Question

Ich habe diesen Code geschrieben, aber es zeigt Time Limit Exceeded. Wie kann ich das schnell machen?

import java.util.*; 
public class Palin{ 
    public static void main(String ar[]){ 
    Scanner input = new Scanner(System.in); 
    String s = input.next(); 
    for(int i = 1 ;i < s.length() ; i++){ 
     if(!(s.substring(0,i).equals(new StringBuilder(s.substring(0,i)).reverse().toString()))){ 
      System.out.print(s.substring(0,i).length()); 
     } 
    } 
    } 
} 

Answer 1

diesen Code anzeigen Es hat

finden Methoden

1. alle möglichen Teile verschiedener Längen
2. Longest Nicht Palindrome Teilzeichenfolge
3. Longest Palindrome String (mit Lambda-Ausdrücke)

Der dritte wurde bereitgestellt, um zu zeigen, wie das Problem mit Lamm gelöst werden kann die Junit Testfälle folgen am unteren

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashSet; 
import java.util.List; 
import java.util.Set; 
import java.util.stream.Collector; 
import java.util.stream.Collectors; 

public class MyStrings { 

    private String s; 
    public MyStrings(String s) { 
     super(); 
     if(s==null||s.trim().length()==0) s=""; 
     this.s = s; 
    } 

    public Set<String> getAllSubStrings() { 

     Set<String> list=new HashSet(); 
     for (int i=0, m=s.length()-1,n=m+1 ;i<=m;i++) { 
      for (int j=i+1;j<=n;j++) 
       list.add(s.substring(i, j)); 
     } 
     return list; 
    } 

    public String getLongestPalindromeSubstr(boolean excludeOriginal) { 
     Set<String> subs = this.getAllSubStrings(); 

     //if original string to be not considered then remove it from the set 
     if (excludeOriginal) 
      subs.remove(s); 

     if(s.isEmpty()) 
      return ""; 

     return subs.stream() 
     .filter(s-> new StringBuilder(s).reverse().toString().equals(s)) 
     .sorted((s1,s2)-> {//sorted in descending order of string length 
      if (s1.length()<s2.length()) return 1; 
      if (s1.length()==s2.length()) return 0; 
      return -1; 
     }) 
     .findFirst() 
     .get(); //return the biggest palindrome substring 

     /* 
     Set<String> subs =this.getAllSubStrings(); 
     System.out.println(subs); 

     List<String> palindromSubStrings = subs.stream() 
     .filter(s-> new StringBuilder(s).reverse().toString().equals(s)) 
     .sorted((s1,s2)-> { 
      //System.out.println("comparing ["+s1+"],["+s2+"]"); 
      if (s1.length()<s2.length()) return 1; 
      if (s1.length()==s2.length()) return 0; 
      return -1; 
     }) //sorted in descending order 
     .collect(Collectors.toList()); 

     System.out.println("palindromSubStrings"+palindromSubStrings); 
     return palindromSubStrings.stream(). 
     findFirst().get(); 
     */ 

    } 
    public String getLongestNonPalindromeSubstr(boolean excludeOriginal) { 
     Set<String> subs =this.getAllSubStrings(); 
     Set<String> nonPalindromes = new HashSet(); 
     for (String str:subs) { 
      if (! new StringBuilder(str).reverse().toString().equals(str)) 
       nonPalindromes.add(str); //remove 
     } 
     //if original string to be not considered then remove it from the set 
     if (excludeOriginal) 
      nonPalindromes.remove(s); 
     System.out.println("Non Palindromes with parent excluded="+excludeOriginal+" is "+nonPalindromes); 
     if (nonPalindromes.isEmpty())return ""; 
     String longest=""; 
     for (String str:nonPalindromes) 
      if(str.length()>=longest.length()) longest=str; 

     return longest;//one of the longest if the set has abc, def, ghi then any one will be returned 
    } 


} 

------ JUnit-Testfall Methoden ---------

@Test 
    public void testAllPossibleSubStrings() { 
     Map<String,String[]> d = new LinkedHashMap(); //data 
     d.put("a", new String[]{"a"}); 
     d.put("aa", new String[]{"a","aa"}); 
     d.put("ab", new String[]{"a","b","ab"}); 
     d.put("abc", new String[]{"a","ab","abc","b","bc"}); 
     d.put("abcd", new String[]{"a","ab","abc","abcd","b","bc","bcd","c","cd"}); 

     d.keySet().forEach(k-> { 
      MyStrings s = new MyStrings(k); 
      Set<String> allSubStrings = s.getAllSubStrings(); 
      //System.out.println(k+"->"+allSubStrings); 
      assertTrue(allSubStrings.containsAll(Arrays.asList(d.get(k)))); 
     }); 
    } 

    @Test 
    public void longestPalindromeSubstring() { 
     System.out.println("largestPalindromeSubstring"); 
     Map<String,Integer> d = new LinkedHashMap(); //data 
     d.put("a", 1); 
     d.put("ab", 1); 
     d.put("abc", 1); 
     d.put("abcc", 2); 
     d.put("abcdcb", 5);//"bcdcb"); 
     d.put("abcbabcd",5); 
     d.put("abc-cbad-dabc-aa",11); 

     d.keySet().forEach(k-> { 
      System.out.println("==========="+k+"==================="); 
      MyStrings s = new MyStrings(k); 
      boolean excludeOriginal = false;    
      String longestPalin = s.getLongestPalindromeSubstr(excludeOriginal); 
      System.out.println("biggestPalinSubstr("+k+")="+longestPalin); 
      assertEquals(longestPalin.length(),(int)d.get(k)); 
     });  
    } 

    @Test 
    public void longestNonPalindromeSubString() { 
     System.out.println("getLongestNonPalindromeSubString"); 
     Map<String,Integer> d = new LinkedHashMap(); //data 
     d.put("a", 0); 
     d.put("ab", 2); 
     d.put("abc", 3); 
     d.put("abcc", 4); 
     d.put("abcdcb", 6);//"bcdcb"); 
     d.put("abcbabcd",8); 
     d.put("abc-cbad-dabc-aa",16); 

     d.keySet().forEach(k-> { 
      System.out.println("==========="+k+"==================="); 
      MyStrings s = new MyStrings(k); 
      boolean excludeOriginal = false; 
      String longestNonPalin = s.getLongestNonPalindromeSubstr(excludeOriginal); 
      System.out.println("longestNonPalin ("+k+")="+longestNonPalin); 
      assertEquals(longestNonPalin.length(),(int)d.get(k)); 
     });  
    } 
    @Test 
    public void longestNonPalindromeSubString2() { 
     System.out.println("getLongestNonPalindromeSubString"); 
     Map<String,Integer> d = new LinkedHashMap(); //data 
     d.put("a", 0); 
     d.put("ab", 0); //a,b are palindromes ab is excluded return 
     d.put("abc", 2); //a,b,c,abc are excluded 
     d.put("abcc", 3); 
     d.put("abcdcb", 5);//"bcdcb"); 
     d.put("abcbabcd",7); 
     d.put("abc-cbad-dabc-aa",15); 

     d.keySet().forEach(k-> { 
      System.out.println("==========="+k+"==================="); 
      MyStrings s = new MyStrings(k); 
      boolean excludeOriginal = true; 
      String longestNonPalin = s.getLongestNonPalindromeSubstr(excludeOriginal); 
      System.out.println("longestNonPalin2 ("+k+")="+longestNonPalin); 
      assertEquals((int)d.get(k),longestNonPalin.length()); 
     });  
    } 

Answer 2

Das sieht mir gut.

import java.util.*; 
public class StackOverFlow{ 
    public static void main(String ar[]){ 
    Scanner input = new Scanner(System.in); 
    String s = input.next(); 
    int length = 0; 
    for(int i = 1 ;i <= s.length() ; i++){ 
     if(!(s.substring(0,i).equals(new StringBuilder(s.substring(0,i)).reverse().toString()))){ 
     length = s.substring(0,i).length(); 
     } 
    } 
    System.out.println(length); 
    } 
}