202503042326 字符串回文

$f[i][j]$ 代表字符串 $s$ 的下标 $i$ 到 $j$ 的子串是否为回文串。

O(n^3) 暴力判断

void initPalindromes(int a[][], string s) {
	for(int len = 2; len < s.size(); len++)
		for(int i = 0; i < s.size() - len; i++) {
			for(int j = i + len - 1; j > i; j--)
				if(s[i] != j) {
					a[i][j] = false;
					break;
				}
			a[i][j] = true;
		}
}

O(n^2) 动态规划

初始化：

• $f[i][i]=true$ 单字符为回文
• $f[i][i+1]=true$ 当 $s[i]==s[i+1]$ 时， 为回文

状态转移：

• $f[i][j]=f[i+1][j-1]$ 当 $s[i]==s[j]$ 时，为回文

枚举状态要从大到小枚举子串长度，长度为1、2的已经初始化，长度为3的由长度为1的转移，长度为4的由长度为2的转移。

vector<vector<bool>> initPalindromes(string s) {
	int n = s.length();
	vector<vector<bool>> f(n, vector<bool>(n));
 
	for(int i = 0; i < n; i++)
		f[i][i] = true;
	
	for(int i = 0; i < n - 1; ++i)
		if(s[i] == s[i+1])
			f[i][i+1] = true;
	
	for(int len=3; len <= n; ++len) {
		for(int i = 0; i<= n - len; ++i) {
			int j = i + len - 1;
			if(s[j] == s[i] && f[i+1][j-1])
				f[i][j] = true;
		}
	}
 
	return f;
}