C# - DP build up length of substring testing each


  • 1

    At first I see the 2-D array and think matrix (rows and columns) this confused me. But then I realized the 2-D array is actually left and right indexes in the string and that led me to see the solution clearly.

    You will be considering substrings starting at left and ending at right (inclusive). To do this you will iterate over all lengths from 1 to n and within each length iterate over staring (or left) position. The key is that you get the answers for a single length at all start positions before going to the next length because the dp depends on the answers from shorter lengths. If you do it this way you will have 3 cases to consider on every iteration, pick the one with the highest value.

    • the answer from removing the left edge char
    • the answer from removing the right edge char
    • and if the left and right chars are equal, 2 plus the answer from removing both left and right

    the 3rd case is how the answer grows. After iterating through all you will have performed O(n^2) checks and used O(n^2) memory, the answer is where left is 0 and right is n-1 which will be your very last calculation.

    To show the 3 cases more clearly I break out lengths 1 and 2 because their logic is simplified.

        public int LongestPalindromeSubseq(string s) 
        {
            int n = s.Length;
            int[,] dp = new int[n,n];
            
            // len 1
            for (int i = 0; i < n; i++) dp[i,i] = 1;
            
            // len 2
            for (int i = 0, j = 1; j < n; i++, j++) dp[i,j] = s[i] == s[j] ? 2 : 1;
            
            // len 3 and up
            for (int len = 3; len <= n; len++)
            {
                for (int i = 0, j = len - 1; j < n; i++, j++)
                {
                    // better of without left or without right
                    int max = Math.Max(dp[i,j-1], dp[i+1,j]);
                    if (s[i] == s[j])
                    {
                        // now check 2 plus without left and without right
                        max = Math.Max(max, 2 + dp[i+1,j-1]);
                    }
                    dp[i,j] = max;
                }
            }
            
            return dp[0,n-1];
        }
    

Log in to reply
 

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