Java >> Java tutorial >  >> Tag >> String

Java-program til at finde det længste palindrom i den givne streng

String

I dette indlæg ser vi et Java-program til at finde det længste palindrom i den givne streng. I den givne streng kan der være mere end ét palindrom, men du skal finde hvilken der er længst og vise den.

For at finde det længste palindrom i strengen skal du starte fra midten af ​​strengen og flytte både til venstre og højre med et tegn og sammenligne disse tegn, hvis de to tegn er lige så betyder det at du har et palindrom og du gør det samme for de næste to tegn. Som eksempel i streng "98189" er centrum 1, og ved at flytte både til venstre og højre og sammenligne kan du se, at 8 og 8 og derefter 9 og 9 er lige store. Samtidig flytter centrum af strengen også i programmet, da du skal finde det længste palindrom i strengen.

En anden ting at overveje er tilfældet, når String er lige, i så fald vil du tage to karakterer som centrum og derefter foretage sammenligningen af ​​karakterer. De to tegn, der betragtes som midterste, skal også være ens.

Java-program til at finde det længste palindrom

public class LongestPal {
  public static void main(String[] args) {
    LongestPal lp = new LongestPal();
    System.out.println("Longest Palindrome- " + lp.findLongestPalindrome("12321981189"));
    System.out.println("Longest Palindrome- " + lp.findLongestPalindrome("toppot"));
    System.out.println("Longest Palindrome- " + lp.findLongestPalindrome("101312321"));
    System.out.println("Longest Palindrome- " + lp.findLongestPalindrome("101311321"));
  }
	
  public String findLongestPalindrome(String str) {
    // starting point for comparison with other palindromes
    String longestPalindrome = str.substring(0, 1);
    for (int i = 0; i < str.length(); i = i+1) {  
      // odd length case (center is i)
      String newPalindrome = checkIfEqual(str, i, i);
      if (newPalindrome.length() > longestPalindrome.length()) {
        longestPalindrome = newPalindrome;
      }
      // even length case (center is i, i+1)
      newPalindrome = checkIfEqual(str, i, i + 1);
      if (newPalindrome.length() > longestPalindrome.length()) {
        longestPalindrome = newPalindrome;
      }
    }	    
    return longestPalindrome;
  }
	
  public String checkIfEqual(String str, int begin, int end) {
    while ((begin >= 0 && end <= str.length() - 1) && (str.charAt(begin) == str.charAt(end))) {
      // move left
      begin--;
      // move right
      end++;
    }
    return str.substring(begin + 1, end);    
  }
}
Output 
Longest Palindrome- 981189
Longest Palindrome- toppot
Longest Palindrome- 12321
Longest Palindrome- 3113

Tidskompleksiteten af ​​denne løsning er O(N 2 ) og rumkompleksitet er O(1) da den samme streng bruges og hukommelseskravet i programmet ikke øges.

Det er alt for emnet Java-program til at finde længste palindrom i den givne streng . Hvis der mangler noget, eller du har noget at dele om emnet, så skriv en kommentar.


Java tag