Longest Palindromic Substring

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.

感觉是很经典的一个题,算法考试考过了,当时不会用dp, 现在用2d dp 来做, time = o(n^2)space = o(n^2),其实可以把space 减到O(N)

  • 每一个字母本身就是palindrome, when i=j, then table[i][j] = true
  • 两个相邻的字母,如果相等,则他们是palindrome, if(i == j+1), table[i][j] = (s.charAt(i)==s.charAt(j))
  • 如果不是两个相邻的字母, 则是dp了, if(i > j+1), table[i][j] = (s.charAt(i) == s.charAt(j))&& table[i-1][j+1]

期中tale【i,j】表示在string中,从index j 到 i是否是palindrome
先算table[0][0]
table[1,0]table[1,1]
table[2,0]table[2,1]table[2,2]
table[3,0]table[3,1]table[3,2]table[3,3]
…….

 
public class Solution {
    public String longestPalindrome(String s) {
        if(s==null) return s;
        boolean[][] table = new boolean[s.length()][s.length()];
        int max = 0;
        int start = 0;
        int end = 0;
        for(int i = 0; i<s.length(); i++){
            for(int j=0; j <= i; j++){
                if(i==j) table[i][j] = true;
                else if(i == j+1) {
                        table[i][j] = (s.charAt(i)==s.charAt(j));
                }else if(i > j+1){
                    table[i][j] = (s.charAt(i) == s.charAt(j))&&table[i-1][j+1];
                }
                if(table[i][j]){
                    if(i-j > max){
                        max = i-j;
                        start = j;
                        end = i;
                    }
                }
            }
        }
        
        return s.substring(start,end+1);
    }
}

DP: space = O(N),

 public class Solution {
    public String longestPalindrome(String s) {
        
        if(s==null) return s;
        
        boolean[] table = new boolean[s.length()];
        int max = 0;
        int start = 0;
        int end = 0;
        
        for(int i = 0; i<s.length(); i++){
            for(int j=0; j <= i; j++){
                if(i==j) table[j] = true;
                else if(i == j+1) {
                        table[j] = (s.charAt(i)==s.charAt(j));
                }else if(i > j+1){
                    table[j] = (s.charAt(i) == s.charAt(j))&&table[j+1];
                }
                if(table[j]){
                    if(i-j > max){
                        max = i-j;
                        start = j;
                        end = i;
                    }
                }
            }
        }
        return s.substring(start,end+1);
    }
}

还有几个可以更好的答案:

  1. 英文解释: O(N)
  2. 中文解释:O(N)
  3. 还有另外一个复杂点的,可以用着个方法O(Nlgn): suffix trees

 

 

 

 
Advertisements

About SemiColon
敢修桥敢铺路敢开山敢放炮,打过老婆打过井,画过图写过检讨, 建过大坝生过娃,化验过离子掏过大粪喝过马尿,骂过丈母娘骂过老板骂过党,打过架下过跪认过耸做过班房.偷过钱偷过心,,睡过西蒙思睡过木板床睡过马路芽子.上过昆仑山下过三叠泉探过溶洞走过罗布泊火焰山里洗个澡.我的人生就是一个一个semicolon分开的. 现在独爱计算机, 不知道下一个是什么;

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: