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

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

DP

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

#include<stdio.h>

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;
}