uopspop

Untitled

Aug 30th, 2020
1,158
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.      * Solution: view this as Dynamic Programming
  7.      * Solution: O(n^2)
  8.      *
  9.      */
  10.     public String longestPalindrome(String s) {
  11.         // check sanity first
  12.         if (s == null || s.isEmpty()) {
  13.             return "";
  14.         }
  15.  
  16.         // initialize
  17.         String result = "";
  18.         String possibleResult = "";
  19.         int len = s.length();
  20.         boolean isP[][] = new boolean[len][len]; // Java all initialized to false by default
  21.  
  22.         // main code
  23.         // odd base case (len == 1): isP[i][i+2] = isP[i+1][i+1] && ( s.charAt(i) == s.charAt(i+2) )
  24.         for (int i = 0; i < len; i++) {
  25.             int left = i;
  26.             int right = i;
  27.             isP[left][right] = true;
  28.  
  29.             // update result
  30.             if (isP[left][right]) {
  31.                 result = giveFinalResult(result, s, left, right);
  32.             }
  33.         }
  34.         // even base case (len == 2): isP[i][i+3] = isP[i+1][i+2] && ( s.charAt(i) == s.charAt(i+3) )
  35.         for (int i = 1; i < len; i++) {
  36.             int left = i-1;
  37.             int right = i;
  38.             if (s.charAt(left) == s.charAt(right)) {
  39.                 isP[left][right] = true;
  40.             }
  41.            
  42.             // update result
  43.             if (isP[left][right]) {
  44.                 result = giveFinalResult(result, s, left, right);
  45.             }
  46.         }
  47.        
  48.         // go - check & build at the same time from small to big
  49.         for (int nowLen = 3; nowLen <= len; nowLen++) {
  50.             int left = 0;
  51.             int right = left + (nowLen - 1); // convert length to index concept
  52.             while (true) {
  53.                 if (right >= len) break;
  54.                
  55.                 isP[left][right] = isP[left+1][right-1] && (s.charAt(left) == s.charAt(right)); // DP
  56.  
  57.                 // update result
  58.                 if (isP[left][right]) {
  59.                     result = giveFinalResult(result, s, left, right);
  60.                 }
  61.  
  62.                 left++;
  63.                 right++;
  64.             }
  65.         }
  66.        
  67.         // get result
  68.         return result;
  69.     }
  70.    
  71.    
  72.     private String giveFinalResult(String nowResult, String s, int left, int right) {
  73.         String result = nowResult;
  74.         String possibleResult = s.substring(left, right+1);
  75.         if (possibleResult.length() > result.length()) {
  76.             result = possibleResult;
  77.         }      
  78.         return result;
  79.     }
  80.    
  81.    
  82. }
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.

×