C# DP solution, optimized space


  • 0
    L

    //bool dp[i][j] is the state of if the string from i to j is a Palindrome.
    //and dp[i][j] only depends on the previous row dp[i][j-1].
    //so we can use one-dimension dp array to save some space.

    public class Solution {
    public int CountSubstrings(string s) {
    int count = 0;
    bool[] dp = new bool[s.Length + 1];
    for(int j = 0; j < s.Length; j++)
    {
    dp[j+1] = true;
    for(int i = 0; i <= j; i++)
    {
    dp[i] = dp[i + 1] && s[i] == s[j];

                if(dp[i])
                {
                    count++;
                }
            }  
        }
        
        return count;
    }
    

    }


Log in to reply
 

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