Minimum insertions to form a palindrome (Memoization)

Given string str, find the minimum number of characters to be inserted to make it a palindrome.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Minimum insertions to form a palindrome, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = None

def count(s, i, j):
  if len(s) <= 1:
    return 0
  
  global cache
  if not cache:
    cache = [[None] * len(s) for _ in range(len(s))]

  if not cache[i][j]:
    cache[i][j] = count(s[1:-1], i + 1, j - 1) if s[0] == s[-1] else min(count(s[1:], i + 1, j), count(s[:-1], i, j - 1)) + 1

  return cache[i][j]

s = 'abcd'

print(count(s, 0, len(s) - 1))

let cache = null;

function count(s, i, j) {
  if (s.length <= 1) {
    return 0;
  }

  if (!cache) {
    cache = Array.from(Array(s.length), () => Array(s.length));
  }

  if (!cache[i][j]) {
    cache[i][j] = (s.at(0) === s.slice(-1)) ? count(s.slice(1, -1), i + 1, j - 1) : Math.min(count(s.slice(1), i + 1, j), count(s.slice(0, -1), i, j - 1)) + 1;
  }

  return cache[i][j];
}

const str = 'abcd';

console.log(count(str, 0, str.length - 1));