RSS

Longest Palindromic Substring [LeetCode 87]

16 Aug

Frequency: ♥ ♥                Difficulty: ♥ ♥ ♥
Data Structure: String
Algorithm: dynamic programming, manacher

Problem Description

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

问题分析

回文问题最经典也是最基础的问题。有兴趣可以参见Longest Palindromic Substring Part I & Part 2。采用暴力搜索检查每个substring是否为回文,需要用O(N^3)。

解法一

采用动态规划,将遍历过的结果记录下来,避免重复的检查。时间和空间复杂度都是O(N^2)。

// O(n^2)
// use a matrix[i][j] (i<=j) to indicate whether 
// the substring of s[i, j] is a palindrome
// matrix[i][j] = matrix[i+1][j-1]&&s.charAt[i]==s.charAt[j] (j-i>=2)
public class Solution {
    public String longestPalindrome(String s) {
        if(s==null||s.length()<=1) return s;
        int length = s.length();
        // will be initialized to false
        boolean[][] matrix = new boolean[length][length];
        int maxLength = 1;
        int l = 0, r = 0;
        for(int j=0;j<length;j++) {
            for(int i=0;i<=j;i++) {
                if(j-i<2&&s.charAt(i)==s.charAt(j)||matrix[i+1][j-1]&&s.charAt(i)==s.charAt(j)) {
                    matrix[i][j] = true;
                    if(maxLength<j-i+1) {
                        l = i;
                        r = j;
                        maxLength = j - i + 1;
                    }
                }
            }
        }
        return s.substring(l, r+1);
    }
}

解法二

中心扩展法,遍历到第i个字符,以它为中心判断回文,以[i, i+1]为中心判断回文。时间负责度为O(N^2),空间负责度为O(1)。

public class Solution {
    public String longestPalindrome(String s) {
        if(s==null||s.length()==0) return "";
        int len = s.length();
        String result = "";
        for(int i=0;i<2*len-1;i++){
            int left = i, right=i/2+1;
            if(i%2==0){
                left=i/2-1;
            }else{
                left=i/2;
            }
            while(left>=0 && right<len && s.charAt(left)==s.charAt(right)){
                left--;
                right++;
            }
            if(right-left-1>result.length()){
                result=s.substring(left+1,right);
            }
        }
        return result;
    }
}

解法三

Manacher算法,首先对字符串进行预处理,在字符串的每个字符前后都加入一个特殊符号,为了避免越界,还需在字符串首尾加上不同的两个特殊字符,经过这样处理后有个好处是原来的偶数长度和奇数长度的回文在处理后的字符串中都是奇数长度。但是由于算法不常见,在面试中考察的可能不大,当做了解。

  • 处理前:1 2 2 1 2 3 2 1
  • 处理后:$   #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #  ^

 

 

查看更多LeetCode解题思路

Advertisements
 
Leave a comment

Posted by on August 16, 2014 in Leetcode

 

Tags: , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

 
%d bloggers like this: