算法（动态规划）：最长回文数
/**
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
注意点：基数回文中心是一个元素。偶数回文中心是两个元素
*/
1.中心扩散法：遍历每个点位中心
//使用中心扩散法得到回文数
+ (NSString *)getPalindromeUseCenterSpread:(NSString *)str {
NSInteger length = str.length;
if (length <= 1) {
return str;
}
NSInteger longestPalindrome = 1;
NSString *longestPalindromeStr = [str substringWithRange:NSMakeRange(0, 1)];
for (int i = 0; i < length; i++) {
NSString *palindromeOdd = [self centerSpread:str indexLeft:i indexRight:i];
NSString *palindromeEven = [self centerSpread:str indexLeft:i indexRight:i+1];
NSString *maxLenth = palindromeOdd.length > palindromeEven.length ? palindromeOdd:palindromeEven;
if (maxLenth.length > longestPalindrome) {
longestPalindrome = maxLenth.length;
longestPalindromeStr = maxLenth;
}
}
return longestPalindromeStr;
}
+ (NSString *)centerSpread:(NSString *)str indexLeft:(NSInteger)indexLeft indexRight:(NSInteger)indexRight{
while (indexLeft >= 0 && indexRight < str.length && [[str substringWithRange:NSMakeRange(indexLeft, 1)] isEqualToString:[str substringWithRange:NSMakeRange(indexRight, 1)]]) {
indexLeft--;
indexRight++;
}
indexLeft++;
indexRight--;
//越界检查 一定注意
if (indexLeft > str.length - 1 || indexRight > str.length - 1) {
return [str substringWithRange:NSMakeRange(str.length-1, 1)];
}
return [str substringWithRange:NSMakeRange(indexLeft, indexRight - indexLeft + 1)];
}
运行：
2.动态规划：解决最优子结构 1.定义状态 2.找到“状态转移方程”
//使用动态规划得到回文数
+ (NSString *)getPalindromeUseDynamicPlanning:(NSString *)str {
NSInteger length = str.length;
if (length <= 1) {
return str;
}
NSInteger longestPalindrome = 1;
NSString *longestPalindromeStr = [str substringWithRange:NSMakeRange(0, 1)];
NSMutableDictionary *dpDic = [NSMutableDictionary dictionary];
for (NSInteger right = 1; right < length; right++) {
for (NSInteger left = 0; left < right; left++) {
NSString *leftStr = [str substringWithRange:NSMakeRange(left, 1)];
NSString *rightStr = [str substringWithRange:NSMakeRange(right, 1)];
if ([leftStr isEqualToString:rightStr] && (right - left <= 2 || [dpDic objectForKey:[NSString stringWithFormat:@"%ld%ld",left+1,right-1]])) {
[dpDic setValue:@"yes" forKey:[NSString stringWithFormat:@"%ld%ld",left,right]];
if (right - left + 1 > longestPalindrome) {
longestPalindrome = right - left + 1;
longestPalindromeStr = [str substringWithRange:NSMakeRange(left, right - left + 1)];
}
}
}
}
return longestPalindromeStr;
}
运行