LeetCode - 5 Longest Palindromic Substring 最长回文子字符串

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Subscribe to see which companies asked this question

初始条件： 1 单个字符是回文 2 紧挨着的两个相同字符也是回文 3 如果两端字符相同，取决于内部子串情况

public class Solution {
    public string LongestPalindrome(string s) {
        if (s == string.Empty || s.Length == 1)
                return s;

            int n = s.Length;
            int longestBegin = 0;
            int maxLen = 1;//单个字符是回文
            bool[,] dp = new bool[n, n];
            char[] sArray = s.ToCharArray();

            //单个字符是回文,正序循环
            for (int i = 0; i < n - 1; i++)
                dp[i, i] = true;

            //紧挨着的两个相同字串也是回文，正序循环
            for (int i = 0; i < n - 1; i++)
            {
                if (sArray[i] == sArray[i + 1])
                {
                    dp[i, i + 1] = true;
                    longestBegin = i;
                    maxLen = 2;
                }
            }

            //考虑到dp的情况，必须从小到大； 所以倒序循环；
            for (int i = n - 3; i >= 0; i--)
                for (int j = i + 2; j < n; j++)
                    if(sArray[i]== sArray[j]&&dp[i+1,j-1])//如果两短字符串相同，则取决于内部子串情况
                    {
                        dp[i, j] = true;
                        if(j-i+1>maxLen)//如果大于最长的，再做修改
                        { 
                            longestBegin = i;
                            maxLen = j - i + 1;
                        }
                    }
            //截取回文
            return s.Substring(longestBegin, maxLen);
            
    }
}
           

注意问题： 考虑到dp[]数组内的内容，最后一遍的循环，需要长度从小到大跑，不能从i，j跨度从大到小；否则就会报错；  原因：

if(sArray[i]== sArray[j]&&dp[i+1,j-1])
           

此处无法进入后半部分的分支；