Welcome~~~


Another blog:
http://fun-st.blogspot.com/

It is easier to write an incorrect program than understand a correct one.

Monday, April 18, 2011

Find the longest palindromes

A clear explanation and solution in (Python, Java, C++):

the most naive solution would be to exhaustively examine all n (n + 1) / 2 substrings of the givenn-length string, test each one if it's a palindrome, and keep track of the longest one seen so far. This has worst-case complexity O(n3), but we can easily do better by realizing that a palindrome is centered on either a letter (for odd-length palindromes) or a space between letters (for even-length palindromes). Therefore we can examine all 2n + 1 possible centers and find the longest palindrome for that center, keeping track of the overall longest palindrome. This has worst-case complexity O(n2).

But this can be done in O(N)






SomeLinks:


A Java Code:

est data used is HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE

  public static string GetPalindromeString(string theInputString) 

{ int j = 0;

          int k = 0;         string aPalindrome = string.Empty;         string aLongestPalindrome = string.Empty ;                   for (int i = 1; i < theInputString.Length; i++)         {             k = i + 1;             j = i - 1;             while (j >= 0 && k < theInputString.Length)             {                 if (theInputString[j] != theInputString[k])                 {                     break;                 }                 else                 {                     j--;                     k++;                 }                 aPalindrome = theInputString.Substring(j + 1, k - j - 1);                 if (aPalindrome.Length > aLongestPalindrome.Length)                 {                     aLongestPalindrome = aPalindrome;                 }             }         }         return aLongestPalindrome;        }


This one is related -- to use the regular expression to detect the palindrome:

--

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥

No comments:

Post a Comment