Algorithm

[LeetCode 5] Longest Palindromic Substring [C] [Runtime : 9 MS]

顿搜

2017-05-24

0 评论

603 阅读

正在检测是否收录...

05/24

1. Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

2. Submission Details

3. Runtime Distribution

4. Example

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

> Input: "cbbd" > Output: "bb" ## 5. Explanation Let dp[i][j] stand for whether S(i, j) is palindromic. > $$for(step : 0 \rightarrow N; \quad i : 0 \rightarrow N - step)$$ > $$j = i + step;$$ > > $$ > dp[i][j] = > \begin{cases} > & true, \quad \text{ if } s[i] == s[j] \&\& step \le 1 \\ > & dp[i+1][j-1],\quad \text{ if } s[i] == s[j] && step > 1 \\ > & false, \quad \text{ if } s[i] != s[j] > \end{cases} > $$ ## 6. Code ```c #include char* longestPalindrome(char* s) { int mLength = strlen(s); int mMaxLength = 0; int mPalindromeStart = 0; int mPalindromeEnd = 0; for (int i = 0; i < mLength -1; i++) { int mStart = i, mEnd = i + 1; for (; mStart >= 0 && mEnd < mLength; mStart --, mEnd ++) { if (s[mStart] != s[mEnd]) { break; } } if (mMaxLength < mEnd - 1 - (mStart + 1) + 1) { mMaxLength = mEnd - 1 - (mStart + 1) + 1; mPalindromeStart = mStart + 1; mPalindromeEnd = mEnd - 1; } mStart = i - 1, mEnd = i + 1; for (;mStart >= 0 && mEnd < mLength; mStart--, mEnd++) { if (s[mStart] != s[mEnd]) { break; } } if (mMaxLength < mEnd - 1 - (mStart + 1) + 1) { mMaxLength = mEnd - 1 - (mStart + 1) + 1; mPalindromeStart = mStart + 1; mPalindromeEnd = mEnd - 1; } } s[mPalindromeEnd + 1] = '\0'; s += mPalindromeStart; return s; } int main() { char s[] = "cbbd"; char * result = longestPalindrome(s); puts(result); system("pause"); return 0; } ```

Array

朗读