leetcode/Algorithms/CPP/5.cpp at master · Accagain2014/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// Author :  Accagain
// Date   :  17/2/14
// Email  :  chenmaosen0@gmail.com

/***************************************************************************************
 * Given a string s, find the longest palindromic substring in s.
 *
 * You may assume that the maximum length of s is 1000.
 *
 * Example:
 *      Input: "babad"
 *      Output: "bab"
 *      Note: "aba" is also a valid answer.
 *
 * Example:
 *      Input: "cbbd"
 *      Output: "bb"
 *
****************************************************************************************/

#include <cstdlib>
#include <cstdio>
#include <iostream>

using namespace std;

/*
 * 注意将字符串翻转，然后求最长公共子串的做法不对，反例 abcdefdcba
 */

class Solution {
public:
    string longestPalindrome(string s) {
        if(s == "")
            return 0;

        int ans = 0;
        int begin, end;

        for(int i=0; i<s.size(); i++)
        {
            int temp = 1;
            //begin = i; end = i;
            if(ans < 1)
            {
                ans = 1;
                begin = i;
                end = i;
            }
            for(int j=1; (i-j>=0) && ((i+j)<s.size()); j++)
            {
                if(s[i-j] == s[i+j])
                {
                    temp += 2;
                    if(temp > ans)
                    {
                        begin = i-j;
                        end = i+j;
                        ans = temp;
                    }

                }
                else
                    break;
            }

            temp = 0;
            for(int j=0; (i>=j) && ((i+j+1)<s.size()); j++) {
                if (s[i - j] == s[i + j + 1])
                {
                    temp += 2;
                    if (temp > ans) {
                        begin = i - j;
                        end = i + j + 1;
                        ans = temp;
                    }
                }
                else
                    break;
            }
        }
        //printf("%d %d %d\n", begin, end, ans);
        return s.substr(begin, ans);
    }
};

int main()
{
    Solution * test = new Solution();
    printf("%s\n", test->longestPalindrome("aaaa").c_str());
    return 0;
}