C# clean & easy to understand DP solution


  • 0
    B

    The difference between mine and others is that I reversed the comparison string so that the DP table can go from top to bottom, instead of bottom up like others. It's just easier for me to understand that way since it makes it similar to other like-problems.

    public class Solution {
        public int LongestPalindromeSubseq(string s) {
            int[,] dp = new int[s.Length + 1, s.Length + 1];
            StringBuilder builder = new StringBuilder();
            
            for(int i = s.Length - 1; i >= 0; i--) {
                builder.Append(s[i]);
            }
            
            string t = builder.ToString();
            
            for(int i = 1; i <= s.Length; i++) {
                for(int j = 1; j <= s.Length; j++) {
                    if(i == 0 || j == 0) {
                        dp[i, j] = 0;
                        continue;
                    }
                    
                    if(s[i-1] == t[j-1]) {
                        dp[i,j] = dp[i-1, j-1] + 1;
                    }
                    else {
                        dp[i,j] = Math.Max(dp[i, j-1], dp[i-1, j]);   
                    }
                }
            }
            
            return dp[s.Length, s.Length];
        }
    }
    

Log in to reply
 

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