最长回文字串 lintcode

浅浅的花香味﹌ 2022-07-16 08:00 180阅读 0赞

package tju.chc;
    
    public class Solution {
    	//方法1  暴力
        /**
         * @param s input string
         * @return the longest palindromic substring
         */
        public String longestPalindrome(String s) {
            // Write your code here
            String res = "";
            int reslen = 0;
            int len = s.length();
            int start = 0;
            for(int i = start; i < len;){
                int j = i;
                while(j < len){
                    int tmplen = j+1 - i;
                    String tmpStr = s.substring(i,j + 1);
                    if(isPalindrome(tmpStr)){
                        if(tmplen > reslen){
                           reslen = tmplen;
                           res = tmpStr;
                        }
                    }
                    j++;
                }
                i++;
            }
            return res;
            
        }
        public boolean isPalindrome(String s){
            int len = s.length();
            int start = 0;
            int end = len - 1;
            while(start < end){
                if(s.charAt(start) != s.charAt(end)){
                    break;            
                }
                start++;
                end--;
            }
            if(start < end)return false;
            else return true;
        }
        
        //方法2 动态规划
        /*
         *     动态规划就是暴力法的进化版本，我们没有必要对每一个子串都重新计算，看看它是不是回文。我们可以记录一些我们需要的东西，
         *     就可以在O（1）的时间判断出该子串是不是一个回文。这样就比暴力法节省了O（N）的时间复杂度哦，嘿嘿，其实优化很简单吧。
         *     P（i，j）为1时代表字符串Si到Sj是一个回文，为0时代表字符串Si到Sj不是一个回文。
         *     P（i，j）= P（i+1，j-1）（如果S[i] = S[j]）。这是动态规划的状态转移方程。
         *     P（i，i）= 1，P（i，i+1）= if（S[i]= S[i+1]）
         */
        public String longestPalindromeDP(String s) {
        	  int n = s.length();
    
        	  int longestBegin = 0;
    
        	  int maxLen = 1;
    
        	  boolean[][] table = new boolean[1000][1000];
    
        	  for (int i = 0; i < n; i++) {
    
        	    table[i][i] = true;   //前期的初始化
    
        	  }
    
        	  for (int i = 0; i < n-1; i++) {
    
        	    if (s.charAt(i) == s.charAt(i + 1)) {
    
        	      table[i][i+1] = true; //前期的初始化
    
        	      longestBegin = i;
    
        	      maxLen = 2;
    
        	    }
    
        	  }
    
        	  for (int len = 3; len <= n; len++) {
    
        	    for (int i = 0; i < n-len+1; i++) {
    
        	      int j = i+len-1;
    
        	      if (s.charAt(i) == s.charAt(j) && table[i+1][j-1]) {
    
        	        table[i][j] = true;
    
        	        longestBegin = i;
    
        	        maxLen = len;
    
        	      }
    
        	    }
    
        	  }
    
        	  return s.substring(longestBegin, longestBegin + maxLen);
    
        	}
        //方法3 中心扩展法
        /*
         * 这个算法思想其实很简单啊，时间复杂度为O（N2），空间复杂度仅为O（1）。就是对给定的字符串S，
         * 分别以该字符串S中的每一个字符C为中心，向两边扩展，记录下以字符C为中心的回文子串的长度。但是有一点需要注意的是，
         * 回文的情况可能是 a b a，也可能是 a b b a。
         */
        public String expandAroundCenter(String s, int c1, int c2) {
    
        	  int l = c1, r = c2;
    
        	  int n = s.length();
    
        	  while (l >= 0 && r <= n-1 && s.charAt(l) == s.charAt(r)) {
    
        	    l--;
    
        	    r++;
    
        	  }
    
        	  return s.substring(l+1, r);
    
        	}
    
        	public String longestPalindromeSimple(String s) {
    
        	  int n = s.length();
    
        	  if (n == 0) return "";
    
        	  String longest = s.substring(0, 1);  // a single char itself is a palindrome
    
        	  for (int i = 0; i < n-1; i++) {
    
        		String p1 = expandAroundCenter(s, i, i);
    
        	    if (p1.length() > longest.length())
    
        	      longest = p1;
    
        	    String p2 = expandAroundCenter(s, i, i+1);
    
        	    if (p2.length() > longest.length())
    
        	      longest = p2;
    
        	  }
    
        	  return longest;
    
        	}
        public static void main(String[] args){
        	Solution solution = new Solution();
        	
        	System.out.println(solution.isPalindrome("a"));
        	System.out.println(solution.longestPalindrome("a"));
        	System.out.println(solution.longestPalindromeDP("a"));
        	
        	System.out.println(solution.isPalindrome("abcdzdcab"));
        	System.out.println(solution.longestPalindrome("abcdzdcab"));
        	System.out.println(solution.longestPalindromeDP("abcdzdcab"));
        	System.out.println(solution.longestPalindromeSimple("abcdzdcab"));
        }
    }