LeetCode题目:Longest Palindromic Substring,二维动态规划

By | 2012 年 9 月 30 日

Updated at 2016-04-28

Question

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.

Analyze

The brute force method will take O(n3) time, and apparently, it will exceed the time limit.

To reduce the time, as we noticed there are a lot of duplicated comparisons in the brute force method, the first thought is dynamic programming. But I was too aggressive at the begging, want to solve this with 1-D dynamic programming in O(n) time.

After find out several exceptional cases with either focus on the start of substring or the end of substring, I realized that it can not fit into a 1-D dynamic programming. But 2-D, can easily beat this question.

2-D Dynamic Programming

Let’s focus on the start index si and end index ei of the substring. When we want answer the question: “Is the substring s[si..ei] palindromic?”, we just check if s[si + 1 .. ei – 1] is palindromic and if s[si] == s[ei]. If both conditions are true, then we can get the positive answer. Then if we solve the problem in this order:

for(int ei = 0; ei < s.length(); ei ++)
  for(int si = ei; si >= 0; si --)
  { // implement here }

Then we can make sure when we resolve sub problem on (si, ei), we know the answer of (si+1, ei-1). So, just build a 2-D matrix and we can beat this question in O(n2) time.

Expand from center

That’s the DP solution. And since it’s O(n2), then there is a more straight forward method with the same time level:
Just at each point in the string S, on the positions of it’s characters like 0,1,2,… or between characters like 0.5, 1.5, … . Then from this position, just expand the substring if it is still palindromic. Then there are O(n) centers and at each center, we need expand O(n) times. Thus, this is also a O(n2) time solution. And simpler.

Codes

Ruby version DP

def longest_palindrome(s)
    map = {}
    max_si, max_ei, max_length = nil, nil, 0
    s.length.times do |ei|
        si = ei
        while si >= 0 do
            if si == ei
                map[ei] = { si => true }
            else
                map[ei][si] = s[ei] == s[si] && (si + 1 >= ei || map[ei - 1][si + 1] == true)
            end

            len = (ei - si + 1)
            if map[ei][si] && len > max_length
                max_length = len
                max_si = si
                max_ei = ei
            end

            si -= 1
        end
    end

    s[max_si..max_ei]
end

Ruby version expand from center

def expand(s, center)
  li, ri = center.floor, center.ceil
  if li == ri
      li -= 1
      ri += 1
  end
  left_space = li
  right_space = s.length - ri - 1
  max_space = [left_space, right_space].min
  most_left = li - max_space
  while li >= most_left do
    if s[li] == s[ri]
      li -= 1
      ri += 1
    else
      break
    end
  end
  #p [ri - li - 1, li + 1, ri - 1]
  [ri - li - 1, li + 1, ri - 1]
end

def longest_palindrome(s)
  i = 0
  max_si, max_ei, max_len = nil, nil, 0
  while i <= s.length - 1 do
    len, si, ei = expand(s, i)
    if max_len < len
        max_si, max_ei, max_len = si, ei, len
    end
    i += 0.5
  end
  s[max_si..max_ei]
end

C++ version DP

class Solution {
public:
    inline void setIsPalindrome(bool * dpmap, int si, int ei, int total_length, bool value) {
        *(dpmap + total_length * ei + si) = value;
    }
    inline bool isPalindrome(bool * dpmap, int si, int ei, int total_length) {
        return *(dpmap + total_length * ei + si);
    }
    string longestPalindrome(string s) {
        int total_length = s.length();
        int max_len = 0, max_si, max_ei;
        bool *dpmap = new bool[total_length * total_length];
        for(int ei = 0; ei < total_length; ei++) {
            for(int si = ei; si >= 0; si--) {
                bool positive = 
                    (si == ei) ||
                    ((s[si] == s[ei]) && ((si == ei - 1) || isPalindrome(dpmap, si + 1, ei - 1, total_length)));
                setIsPalindrome(dpmap, si, ei, total_length, positive);
                if(positive){
                    int len = ei - si + 1;
                    if(max_len < len){
                        max_len = len;
                        max_si = si;
                        max_ei = ei;
                    }
                }
            }
        }
        delete dpmap; dpmap = NULL;
        return s.substr(max_si, max_len);
    }
};

旧版,有误,奇怪的是当初竟然通过了测试…

问题要求是寻找一个字符串中的最长可逆子串,可以转化为求它和自身的逆序串的最长公共子串问题。
关键的思路是:
用一个matrix记录最长公共子串的长度,mat[i][j]表示以a串的i-1字符结束且以b串的j-1字符结束的最长子串长度。
当stringa[i-1] == stringb[j-1]时,mat[i][j] == mat[i-1][j-1] + 1

其中遇到了两个问题:
1.在子函数longestCommonSub中,如果先new,在得到最长公共串之后delete申请的空间mat的话,运行到大概第5个test case的时候会报runtime error。
2.在代码段

if(max <= len)

中,如果把小于等于改成小于,在大测试集合中会有一个莫名其妙的test case结果错误。
这两个问题都不知道原因。



代码:1488ms过大集合

class Solution {
public:
    string longestCommonSub(string &sa, string &sb) {
        int rows = sa.size() + 1;
        int cols = sb.size() + 1;
        static int *mat = NULL;
        if(NULL == mat) {
            mat = new int[1001 * 1001];
        }
        for(int ir = 0 ; ir < rows; ++ ir) {
            for(int ic = 0 ; ic < cols; ++ ic) {
                *(mat + ir * cols + ic) = 0;
            }
        }
        int max = 0;
        int maxIr;
        for(int ir = 1 ; ir < rows; ++ ir) {
            char sai = sa[ir - 1];
            for(int ic = 1 ; ic < cols; ++ ic) {
                if(sai == sb[ic - 1]){
                    int len = 1 + *(mat + (ir-1) * cols + ic - 1);
                    *(mat + ir * cols + ic) = len;
                    if(max <= len) {
                        max = len;
                        maxIr = ir;
                    }
                }
            }
        }
        string result;
        if(max > 0) {
            result = sa.substr(maxIr - max, max);
        }
        return result;
    }
    string longestPalindrome(string s) {
        string rs = s;
        for( int i = 0 ; i < s.size(); ++ i) {
            rs[i] = s[s.size() - 1 - i];
        }
        return longestCommonSub(s,rs);
    }
};

2 thoughts on “LeetCode题目:Longest Palindromic Substring,二维动态规划

  1. blurjp

    “寻找一个字符串中的最长可逆子串,可以转化为求它和自身的逆序串的最长公共子串问题。”这个假设是错的。

    S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.
    The longest common substring between S and S’ is “abacd”. Clearly, this is not a valid palindrome.

    Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注