5. Longest Palindromic Substring

这道题常规做法,从任意位置向两边扫描,http://www.programcreek.com/2013/12/leetcode-solution-of-longest-palindromic-substring-java/
的解释非常容易懂。

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() == 0) return null;
        int maxLength = 1;
        String longestPalindrome = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            String temp = helper(s, i, i);
            if (temp.length() > longestPalindrome.length()) {
                longestPalindrome = temp;
            }
        }
        for (int i = 0; i < s.length(); i++) {
            String temp = helper(s, i, i + 1);
            if (temp.length() > longestPalindrome.length()) {
                longestPalindrome = temp;
            }
        }

        return longestPalindrome;
    }

    private String helper(String s, int begin, int end) {
        while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
            begin--;
            end++;
        }
//注意substring的用法,"babad"的substring(0,2)是"ba",所以这里end不用-1
        return s.substring(begin+1, end);
    }
}

第二种做法DP,思维难度也不大,状态转移方程:

                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;

但是做起来花了很多时间,首先要知道,这里只需要管上三角矩阵的值,因为j>=i的。我甚至连上三角矩阵的判断方法都想不明白。。思维迟钝。有点失望。其次,i要从后往前扫,否则会出现一种情况,aaaa,从0到4的过程中要用到从2到3,如果i从0开始,内层的就还没有检查过。

DP的复杂度也是O(n*n)。
好fin,这题搞了三小时,我真觉得不可思议,就坐在这电脑前3小时。。看这dp。。第一种方法做出来之后注意力不集中了。

http://blog.csdn.net/linhuanmars/article/details/20888595

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,774评论 0 33
  • 动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...
    廖少少阅读 3,336评论 0 18
  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 17,934评论 2 36
  • 《行走》 行走在旷野中 拥抱自然 风吹过 我明白什么是自由 行走在生活中 感受生命 人来过 我明白什么是爱 行走的...
    诗人安阅读 225评论 3 1
  • 好几天都没有那么想你了,日子不就还这样过的好好的嘛,呵呵,,,
    相逢是孤岛阅读 267评论 0 0