c# solution: 1d dp array, local & global


  • 0
    B
    public class Solution 
    {
        public string LongestPalindrome(string s) 
        {
            if (s.Length == 1) return s;
            var n = s.Length;
            var dp = new int[n];
    
            for (int i = 0; i < n; i++)
            {
                dp[i] = 1;
            }
    
            var global = 0;
            var globalLeft = 0;
    
            for(int i = 1; i < n; i++)
            {
                for(int j = 0; j < i; j++)
                {
                    if (s[j] != s[i])                       dp[j] = 1;
                    else if (s[j] == s[i])
                    {
                        if (i - j == 1)         dp[j] = 2;
                        else if (i - j == 2)    dp[j] = 3;
                        else if (dp[j+1] == (i - 1) - (j + 1) + 1)
                        {
                            dp[j] = dp[j+1] + 2;
                        }
                        else
                        {
                            dp[j] = 1;
                        }
                    }
                    
                    var local = dp[j];
    
                    if (local > global)
                    {
                        globalLeft = i - dp[j] + 1;
                        global = dp[j];
                    }
                }
            }
    
            var result = s.Substring(globalLeft, global);
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.