本文共 1443 字，大约阅读时间需要 4 分钟。

Objective-C实现最长回文子序列算法

在 Objective-C 中实现最长回文子序列（Longest Palindromic Subsequence，LPS）算法可以使用动态规划的方法。以下是一个完整的实现代码示例，以及详细的代码解释。

代码实现

#import 
   
    
@interface Solution : NSObject(NSInteger)longestPalindromicSubsequence:(NSString *)s;
@end
@implementation Solution
- (NSInteger)longestPalindromicSubsequence:(NSString *)s {
    if (s == nil || s.length == 0) {
        return 0;
    }
    
    // 定义动态规划表格，dp[i][j]表示子序列s[0..i-1]和s[j..n-1]的最长回文子序列长度
    int n = s.length;
    int **dp = (int **)malloc(n * n);
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1; // 单个字符的最长回文子序列长度为1
    }
    
    // 遍历所有可能的子序列起始和结束位置
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (s[i] == s[j]) {
                if (i == j) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i+1][j-1] + 2;
                }
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    
    return dp[0][n-1];
}
@end
   

代码解释

总结

通过动态规划的方法，我们可以高效地解决最长回文子序列问题。该算法的时间复杂度为 O(n^2)，适用于处理较短的字符串。对于更长的字符串，可以考虑使用更高效的算法如Manacher算法或中心扩展法。