C# O(n2) solution sharing two ways(middle scan and DP)


  • 0
    Y
    //from middle scan
    public class Solution {
        public string LongestPalindrome(string s) {
            int n=s.Length;
            if(n<2)
                return s;
            int staIn=0,max=1;
            for(int i=0;i<n-1;i++)
            {
                int dist=findLongest(s,i,i);
                int dist2=findLongest(s,i,i+1);
                if(dist*2+1>max)
                {
                    max = dist*2+1;
                    staIn = i-dist;
                }
                if(dist2*2>max)
                {
                    max=dist2*2;
                    staIn=i-dist2+1;
                }
            }
            return s.Substring(staIn,max);
        }
        private int findLongest(string s, int i,int j)
        {
            int dist=0;
            while(i-dist>=0&&j+dist<=s.Length-1)
            {
                if(s[i-dist]!=s[j+dist])
                    return j==i?dist-1:dist;
                dist++;
            }
            return j==i?dist-1:dist;
        }
    }
    

    //DP

    public class Solution {
        public string LongestPalindrome(string s) {
            //DP O(n2)
            int n=s.Length;
            bool[,] DP=new bool[n,n];
            int max=0,staInd=0;
            for(int k=0; k < n; k++)
            {
                for(int i = 0; i < n - k;i++)
                {
                    if(s[i] == s[i+k] && (k < 2 || DP[i+1,i+k-1]))
                    {
                        DP[i,i+k]=true;
                    }
                    else
                    {
                        DP[i,i+k]=false;
                    }
                    
                    if(DP[i,i+k]&&k+1>max)
                    {
                        max = k + 1;
                        staInd = i;
                    }
                }
            }
            return s.Substring(staInd,max);
        }
    }

Log in to reply
 

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