第五题

作者: cde99bf0b5b1 | 来源:发表于2017-09-18 19:46 被阅读0次

解法一:

class Solution {
public:
    string longestPalindrome(string s) {
        int max_len = 0;
        string res = "";
        int ls = s.size();
        int i, j, k;
        for(i = 0; i < ls; i++){
            findpal(s,i-1,i+1,max_len,res);
        }
        for(i = 0; i < ls; i++){
            findpal(s, i, i + 1, max_len, res);
        }
        return res;
    }
    
private:
    void findpal(string s, int j, int k, int &max_len, string &res){
        while(j >= 0 && k <= s.size()-1 && s[j] == s[k]){
            j--;
            k++;
        }
        if(max_len < k - j -1){
            max_len = max(max_len, k - j - 1);
            res = s.substr(j + 1, max_len);
        }
    }
};

解法二:

#include <string>
using std::string;

class Solution {
public:
    string longestPalindrome(string s) {
        int max_len = 1;
        string res = "";
        const int ls = s.size();
        bool **dp = new bool*[ls];
        for (size_t i = 0; i < ls; ++i)
        {
            dp[i] = new bool[ls];
        };
        res = s.substr(0,1);
        for(int i = 0; i < ls;i++){
            dp[i][i] = true;
        }
        for(int i = 0; i < ls-1;i++){
            if(s[i]==s[i+1]){
                dp[i][i+1] = true;
                if(max_len != 2){
                    max_len = 2;
                    res = s.substr(i,2);
                }
            }
            else dp[i][i+1] = false;
        }
        for(int j = 2; j < ls; j++){
            for(int i = 0; i < ls-j; i++){
                if(dp[i+1][j-1] && (s[i]==s[j])){
                    dp[i][j] = true;
                    int temp = j - i + 1;
                    if(temp > max_len){
                        max_len = temp;
                        res = s.substr(i,temp);
                    }
                }
                else dp[i][j] = false;
            }
        }
        return res;
    }
};

相关文章

  • 语文教师的情怀——魏书生《教学工作漫谈》读后反思006

    第6天 《初中推普五题》《除了教材,还讲什么》 今天学习魏书生老师的两篇文章:《初中推普五题》和《除了教材,还讲什...

  • 刘禹锡《金陵五题》(2019-12-15)

    刘禹锡《金陵五题》 金陵五题(并序) 余少为江南客,而未游秣陵,尝有遗恨。后为历阳守,跂而望之。适有客以《金陵五题...

  • 过年五题

    又近年关,这组“过年五题”是去年过年所写。现在读来,感慨年年岁岁,愿岁月静好。 过年五题 --------...

  • 30. 历程五题(组诗)

    历程五题(组诗) 历程五题(组诗) 徐 宏 〈一〉紫色的凄迷 一些罪恶的砝码 加重了生命的天平 让一颗悲痛...

  • 黄粱录

    黄粱录 by相公痴 原身:《那些年我模仿过的鲁迅语录》 初代:《第x次模仿鲁迅先生写五题》 从2016年写起,中途...

  • 2019.1.21《教学工作漫谈》一9《初中推普五题》10《除了

    2019年1月21日星期一 1.读原文:《初中推普五题》《除了教材还讲什么》 2.心得: 《初中推普五题》 课前朗...

  • 隐藏在安慰背后的否定

    女儿做完了历史试卷的选择题,发现错了五个非常恼火,说:“怎么会错了五题呢?” 我安慰她说,“不就错了五题嘛,你大部...

  • 56

    晚上8点。 我:8点到了,每日五题时间到了。 她:等我吃完这个橙子。 我:我们的约定是八点开始做每日五题。 她:妈...

  • lintcode 翻转链表

    三十五题为翻转一个单链表,三十六题为翻转链表中第m个节点到第n个节点的部分样例给出链表1->2->3->4->5-...

  • 五题

    在人世间,我们会遇到很多人,并且因为缘分而成为朋友,但是这需要二人的维持,别到了僵的地步。 那么请记住拥有一个脾气...

网友评论

      本文标题:第五题

      本文链接:https://www.haomeiwen.com/subject/tlabsxtx.html