2016年8月27日星期六

Longest Palindromic Substring vs Longest Palindromic Subsequence

Longest Palindromic Substring
      f[i][j] means string[i...j] is palindromic.
        thus, f[i][j] = true if str[i] == str[j] && f[i + 1][j - 1] = true

Longest Palindromic Subsequence
        g[i][j] means the maximum length of palindromic subsequence in string[i...j]
        thus, g[i][j] = max(g[i + 1][j - 1] + 1 (if str[i] == str[j]),
                                     g[i + 1][j],
                                     g[i][j - 1]);


没有评论:

发表评论