Added other dynamic programming solutions for count palindromes

anxious-coder-lhs · anxious-coder-lhs · commit 38338fa85052 · 2020-10-23T13:27:34.000+05:30
diff --git a/dynamic_programming/CountOfPalindromicSubstrings.ts b/dynamic_programming/CountOfPalindromicSubstrings.ts
@@ -64,36 +64,77 @@ class PalindromicSubstringsCounter {
         return result.size;
     }
 
+    countDPTopDown(input: string) {
+
+        const result: Set<string> = new Set();
+
+        function countHelper(input: string, beg: number, end: number, dp: boolean[][]) {
+
+            // Base Conditions where the palindrome is valid
+            if (end < beg) return true;
+            if (end == beg) {
+                result.add(`${beg}|${end}`);
+                dp[beg][end] = true;
+                return true;
+            }
+
+            if (dp[beg][end] !== undefined) {
+                return dp[beg][end];
+            }
+    
+            countHelper(input, beg, end - 1, dp)
+            countHelper(input, beg + 1, end, dp)
+
+            // Case: checking if the strings are palindrome using extremes matching and recursive substring.
+            if (input[beg] === input[end] && countHelper(input, beg + 1, end - 1, dp)) {
+                result.add(`${beg}|${end}`);
+                dp[beg][end] = true;
+                return true;
+            } else { 
+                return false;
+            }
+        }
+
+        countHelper(input, 0, input.length - 1, Array.from({length: input.length}, () => Array(input.length)));
+        // console.log(result)
+ 
+        return result.size;
+    }
+
+    /**
+     * Similar as the recursive brute force solution, but we also use memoization to save the pre-computed results.
+     * 
+     * Time: O(n^2) since the results are computed at least once for each possible pair of beg and end.
+     * Space: O(n^2) + O(n) for storing the memoized results and also the recursion depth.
+     * 
+     * @param input 
+     */
     countDPBottomsUp(input: string) {
 
         // Create a DP table defining the number of valid palindromic strings for the substrings starting at (row) and ending at (col).
-        const dp: number[][] = Array.from({length: input.length + 1}, () => Array(input.length).fill(0));
+        const dp: boolean[][] = Array.from({length: input.length}, () => Array(input.length).fill(false));
 
         // Init boundary conditions (for each substring starting and ending at the idx position, there is only 1 valid palindrome.)
-        for (let idx = 0; idx < input.length; idx++) dp[idx][idx] = 1;
-
-        /**   a b c d
-         * a [1 2 3 4
-         * b    5 6 2]
-         * c      4 1
-         */
+        for (let idx = 0; idx < input.length; idx++) dp[idx][idx] = true;
 
+        let total = input.length;
+        
         // Build the solution for all character range. DP row represents the starting char and col represents the ending char.
-        for (let beg = input.length; beg >= 0; beg--) {
+        for (let beg = input.length - 1; beg >= 0; beg--) {
             for (let end = beg + 1; end < input.length; end++) {
-
-                // Case 1: If the extremes are matching
-                    // If the substring at beg + 1:end - 1 are matching, we update 1 to the counter.
-                    // If the susbtrings are not matching, we dont have a palindrome, take the last one.
-                if (input[beg] === input[end]) {
-                    dp[beg][end] = dp[beg + 1][end - 1];
+                if (input[beg] === input[end] && beg + 1 === end) {
+                    // If the 2 extremes are equal and there is nothing in between
+                    dp[beg][end] = true
+                    total++
+                } else if (input[beg] === input[end] && dp[beg + 1][end - 1]) {
+                    // If the extremes are matching, we need to ensure the left over substrings are also creating a palindrome
+                    dp[beg][end] = true
+                    total++
                 }
-
-                dp[beg][end] += dp[beg + 1][end];
             }
         }
 
-        return dp[0][input.length - 1];
+        return total;
     }
 
     /**
@@ -103,7 +144,7 @@ class PalindromicSubstringsCounter {
      * @param end 
      */
     isValidPalindrome(input: string, beg: number, end: number) {
-        while(end >= beg) {
+        while(end >= beg) { 
             if (input[end--] !== input[beg++]) return false;
         }
 
@@ -115,7 +156,8 @@ function testCountPalindromeSubstring(input: string) {
     const counter = new PalindromicSubstringsCounter();
     console.log(`Counter BF for input: ${input} returned: ${counter.countBF(input)}`);
     console.log(`Counter BF Recursive for input: ${input} returned: ${counter.countBFRecursive(input)}`)
-    // console.log(`Counter DP bottoms up for input: ${input} returned for ${counter.countDPBottomsUp(input)}`);
+    console.log(`Counter DP Top down for input: ${input} returned: ${counter.countDPTopDown(input)}`)
+    console.log(`Counter DP bottoms up for input: ${input} returned for ${counter.countDPBottomsUp(input)}`);
 }
 
 testCountPalindromeSubstring("abdbca")
