LeetCodeSolution/5.LongestPalindromicSubstring.cpp at master · fulinli/LeetCodeSolution · 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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/*
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"
*/
//Solution1为暴力法，超出时间限制。
class Solution1
{
  public:
    string longestPalindrome(string s)
    {
        string str;
        int length;
        for (int i = 0; i < s.length(); i++)
        {
            for (int j = i + 1; j <= s.length(); j++)
            {
                cout << "**********" << endl;
                cout << "i = " << i << ", j = " << j << endl;
                cout << "s.substr(i, j)=" << s.substr(i, j - i) << endl;
                if (isPalindromic(s.substr(i, j - i)))
                {
                    length = j - i;
                    cout << "length=" << length << endl;
                    if (str.length() <= length)
                        str = s.substr(i, j - i);
                }
            }
        }
        return str;
    }
    bool isPalindromic(string s)
    {
        cout << "string s = " << s << endl;
        bool isPalindromicstr;
        for (int k = 0; k < s.length(); k++)
        {
            if (s[k] == s[s.length() - k - 1])
                isPalindromicstr = true;
            else
            {
                isPalindromicstr = false;
                break;
            }
        }
        cout << "isPalindromicstr=" << isPalindromicstr << endl;
        return isPalindromicstr;
    }
};
//"dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd" 测试超过时间限制
//Solution2
//2018-7-25通过学习，使用了动态规划方法，写的混乱，未通过。
//2018-7-28修改后，应该是可以通过的，可是leetcode报错，执行代码可以通过，提交解答未通过
class Solution2 {
public:
    string longestPalindrome(string s)
    {
        string str;
        int maxlength = 1;
        int strlength = s.length();
        int dp[1000][1000];
        for(int i = 0; i < strlength; i++)
        {
            dp[i][i] = 1;
            if(maxlength<=1)
                str = s.substr(i, 1);
            if(i<=strlength-1)
            {
                if(s[i+1] == s[i])
                {
                    dp[i][i+1] = 1;
                    maxlength = 2;
                    str = s.substr(i, 2);
                }
            }
        }
        for(int L = 3; L <= strlength; L++)
        {
            for(int j = 0; j < strlength - L + 1; j++)
            {
                if((s[j] == s[L+j-1]) && dp[j+1][L+j-2]==1)
                {
                    dp[j][L+j-1] = 1;
                    if(L>=maxlength)
                    {
                        str = s.substr(j, L);
                        maxlength = L;
                    }
                }
            }
        }
        return str;
    }
};
//基本方法沿用solution2，没有用静态数组，采用动态数组后提交通过。
class Solution3 {
public:
    string longestPalindrome(string s) {
        string str;
        int maxlength = 1;
        int strlength = s.length();
        //*********************************************************************
        vector<vector<int> > dp(s.length(),vector<int>(s.length()));
        //*********************************************************************
        //int dp[1000][1000];
        for(int i = 0; i < strlength; i++)
        {
            dp[i][i] = 1;
            if(maxlength<=1)
                str = s.substr(i, 1);
            if(i<=strlength-1)
            {
                if(s[i+1] == s[i])
                {
                    dp[i][i+1] = 1;
                    maxlength = 2;
                    str = s.substr(i, 2);
                }
            }
        }
        for(int L = 3; L <= strlength; L++)
        {
            for(int j = 0; j < strlength - L + 1; j++)
            {
                if((s[j] == s[L+j-1]) && dp[j+1][L+j-2]==1)
                {
                    dp[j][L+j-1] = 1;
                    if(L>=maxlength)
                    {
                        str = s.substr(j, L);
                        maxlength = L;
                    }
                }
            }
        }
        return str;
    }
};