202408201507
tags: #dfs #dp

var isValidPalindrome = function(s, k) {
	const memo = new Map();
	
	const isValid = (start, end) => {
		const key = start + "-" + end;
		if (memo.has(key)) {
			return memo.get(key);
		}
		let mistakes;
		if (start === end) {
			mistakes = 0;
		} else if (end - start === 1) {
			mistakes = s[start] === s[end] ? 0 : 1;
		} else if (s[start] === s[end]) {
			mistakes = isValid(start + 1, end - 1);
		} else {
			mistakes = 1 + Math.min(isValid(start + 1, end), isValid(start, end - 1));
		}
		memo.set(key, mistakes);
		return mistakes;
	}
	
	return isValid(0, s.length - 1) <= k;
};

Reference

https://leetcode.com/problems/valid-palindrome-iii