力扣题解（分割回文串IV）

1745. 分割回文串 IV

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

思路：本题要去的是分成三部分，最暴力的做法是中间分一部分是回文串，然后看两边是否是回文串。优化是对判断两边是否是回文串进行快速判断。因为可以在o（N）时间内求出来所有位置为中心的最长回文串长度，则此时当（j，i）为一个回文串，判断（0-j-1）和（i+1，n-1）位置是否是回文串时，可以只需要判断（0，i-1）的中心位置的最大回文串是否能包含（0，i-1）即可，对于右半部分一样。注意，由于回文串可能是奇数个字符组成，也可能是偶数个字符组成，故分别求出以i位置为中心，奇数个最大长度和偶数个最大长度。然后对于（0，j-1），需要先判断是奇数个还是偶数个，然后用对应的最大长度判断即可。

class Solution { public: 		bool judge(vector<int>&dp1, vector<int>&dp2, int left, int right) 				{  					if ((right -left+1) % 2 == 0) 						return dp2[(right +left) / 2] >= right - left+1; 					else 						return dp1[(right + left) / 2] >= right - left+1;  				}  		  			bool checkPartitioning(string s) {  				int n = s.size(); 				vector<int>dpone(n, 1); 				vector<int>dptwo(n, 0); 				for (int i = 0; i < n; i++) 				{ 					int j = 1; 					while (i - j>= 0 && i + j < n && s[i - j] == s[i + j]) 					{ 						dpone[i] += 2; 						j++; 					} 					j = 0; 					while (i - j >= 0 && i + 1 + j < n && s[i - j] == s[i + j + 1]) 					{  						dptwo[i] += 2; 						j++; 					} 				} 				//此时dpone[i]表示以i为中心？的最长回文串长度 				//dotwo表示以i，i+1为中心的最长回文子串长度  				for (int i = 0; i < n - 1; i++) 				{ 					int j = 0; 					while (i - j-1 >= 0 && i + 1 + j < n && s[i - j] == s[i + j]) 					{ 						if (judge(dpone, dptwo, 0, i - j - 1) && judge(dpone, dptwo, i + j + 1, n - 1)) 							return true; 						j++; 					} 					j = 0; 					while (i - j >= 0 && i + 1 + j < n && s[i - j] == s[i + j + 1]) 					{  						if (judge(dpone, dptwo, 0, i - j - 1) && judge(dpone, dptwo, i + j + 2, n - 1)) 							return true; 						j++; 					} 				} 				return false; 			} };