uopspop

Untitled

Aug 30th, 2020
1,109
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class Solution {
  2.     /**
  3.      * @param s: input string
  4.      * @return: a string as the longest palindromic substring
  5.      */
  6.     public String longestPalindrome(String s) {
  7.         // write your code here
  8.         String result = "";
  9.        
  10.         // check sanity first
  11.         if (s == null || s.isEmpty()) {
  12.             return "";
  13.         }
  14.        
  15.         // main code
  16.         int len = s.length();
  17.        
  18.         // extract certain part of original string as substrings
  19.         for (int start = 0; start < len; start++) { // layer 1: O(n)
  20.             for (int end = start; end < len; end++) { // layer 2: O(n)
  21.                
  22.                 // verify if palindromic
  23.                 int left = start;
  24.                 int right = end;
  25.                 boolean isAllMateched = false;
  26.                 while (true) { // layer3: O(n)
  27.                    
  28.                     if (left > right) {
  29.                         isAllMateched = true;
  30.                         break;
  31.                     }
  32.                    
  33.                     if (s.charAt(left) != s.charAt(right)) {
  34.                         isAllMateched = false;
  35.                         break;
  36.                     }
  37.                    
  38.                     left++;
  39.                     right--;
  40.                 }
  41.                
  42.                 // System.out.println("start: " +  start);
  43.                 // System.out.println("end: " +  end);
  44.                
  45.                 // if all matched
  46.                 if (isAllMateched) {
  47.                     String possibleResult = s.substring(start, end+1);
  48.                     // check if longer
  49.                     if (possibleResult.length() > result.length()) {
  50.                         result = possibleResult;
  51.                     }
  52.                 }
  53.             }
  54.         }
  55.        
  56.         // get result
  57.         return result;
  58.     }
  59. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×