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])
           

此處無法進入後半部分的分支；