Typescript top-down dynamic programming detailed solution. Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nA Palindrome string is one that reads the same forward and backward. One way to determi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nA Palindrome string is one that reads the same forward and backward. One way to determine if a string is palindromic is by using a **two-pointer algorithm**. In this case, we use two pointers, one at the start of the string and the other at the end of the string, and then we start comparing the characters at both pointers as we move the pointers.\n\nWe can use this same idea to determine the number of insertions required to make a string a palindrome.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nOur approach involves using two pointers, one on the first index `[i]` and the other on the last index `[j]`. We move the pointers based on the following rules:\n\n- If the characters at both pointers are the same (i.e `s[i] === s[j]`), we move both pointers forward `(i++, j--)`, and no insertion operation is necessary.\n- If the characters at both pointers are NOT the same (i.e `s[i] !== s[j]`), we have two options:\n\n    - We move the first pointer and leave the second pointer `(i++, j)`, and increment the number of operations by 1. This operation is equivalent to inserting one character before index `j`(i.e `j+1`) that matches the one at index `i`.\n    - We move the second pointer and leave the first pointer `(i, j--)`, and increment the number of operations by 1. This operation is equivalent to inserting one character before index `i` (i.e `i-1`) that matches the one at index `j`.\n\n\nTo implement this approach, we wrote a recursive function that keeps track of both pointers and a cache to optimize the solution by storing the results for all pointer pairs to avoid duplicate computations.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n^2)$$\nn = length of string (s.length)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n^2)$$\n\n# Code\n```\nfunction minInsertions(s: string): number {\n    const cache: number[][] = new Array(501);\n\n    for(let i = 0; i < cache.length; i++){\n        cache[i] = new Array(501).fill(-1);\n    }\n\n    return helper(0, s.length - 1);\n\n    function helper(i: number, j: number): number {\n        if(i >= j){\n            return 0;\n        }\n        if(cache[i][j] !== -1){\n            return cache[i][j];\n        }\n\n        let min: number = Number.MAX_VALUE;\n\n        if(s[i] === s[j]){\n            min = Math.min(min, helper(i+1, j-1));\n        } else {\n            min = Math.min(\n                min,\n                helper(i+1, j) + 1,\n                helper(i, j-1) + 1\n            );\n        }\n\n        cache[i][j] = min;\n        return min;\n    }\n};\n```
['Two Pointers', 'Dynamic Programming', 'TypeScript']