5.最长回文子串

/*
 * @lc app=leetcode.cn id=5 lang=typescript
 *
 * [5] 最长回文子串
 */

// @lc code=start
// 动态规划法
// function longestPalindrome(s: string): string {
// 	let len = s.length;
// 	// 初始化dp表
// 	let dp = Array.from({ length: len }, () =>
// 		Array.from({ length: len }, () => false)
// 	);
// 	let maxStr: string = ``;
// 	for (let i = len - 1; i >= 0; i--) {
// 		for (let j = i; j < len; j++) {
// 			dp[i][j] = s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1]);
// 			if (dp[i][j] && j - i >= maxStr.length) {
// 				maxStr = s.slice(i, j + 1);
// 			}
// 		}
// 	}
// 	return maxStr;
// }

// 双指针法
function longestPalindrome(s: string): string {
	let maxStr = "";
	let l = 0;
	while (l < s.length) {
		let r = s.length - 1;
		while (l <= r && r - l >= maxStr.length) {
			// 判断当前是否为回文
			if (isPalind(s.slice(l, r + 1))) {
				maxStr = s.slice(l, r + 1);
			}
			r--;
		}
		l++;
	}
	return maxStr;
}

// 判断是否为回文
function isPalind(s: string): boolean {
	for (let i = 0; i < s.length; i++) {
		let j = s.length - 1 - i;
		if (s[i] != s[j]) {
			return false;
		}
	}
	return true;
}
console.log(longestPalindrome("aacabdkacaa"));

// @lc code=end