【代码随想录】【算法训练营】【第52天】 [647]回文子串 [516]最长回文子序列

前言

思路及算法思维，指路代码随想录。
题目来自 LeetCode。

day 52，周五，开始补作业了~

题目详情

[647] 回文子串

题目描述

647 回文子串

解题思路

前提：寻找回文子串，子串意味着元素连续
思路：动态规划寻找dp数组之间有联系的推导关系， dp[i][j]: 字符串中[i, j]子串是否为回文子串，s[i] == s[j]时, 3种情况, ij时,true, i+1j时,true, j>i+1时,dp[i][j] = dp[i+1][j-1]， s[i] != s[j]时, dp[i][j] = false，统计dp数组中true的数量
重点：dp数组的定义、递推公式的推导、回文子串的条件判断

代码实现

C语言

动态规划

// 动态规划 dp[i][j]: 字符串中[i, j]子串是否为回文子串
// s[i] == s[j]时, 3种情况, i==j时,true, i+1==j时,true, j>i+1时,dp[i][j] = dp[i+1][j-1]
// s[i] != s[j]时, dp[i][j] = false
// 统计dp数组中true的数量

int countSubstrings(char* s) {
    int sLen = strlen(s);
    bool dp[sLen][sLen];
    int count = 0;
    // 遍历
    for (int i = sLen - 1; i >= 0; i--) {
        for (int j = i; j < sLen; j++) {
            if (j == i) {
                dp[i][j] = true;
            } else if (j == i + 1) {
                if (s[i] == s[j]) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = false;
                }
            } else {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = false;
                }
            }
            if (dp[i][j] == true) {
                count++;
            }
        }
    }
    return count;
}

双指针

// 双指针: 2种情况
// 以单个元素为核心向两边扩展,寻找回文子串的个数
// 以两个元素为核心向两边扩展,寻找回文子串的个数

int checkSubStrings(char *s, int sLen, int i, int j)
{
    int res = 0; 
    while (i >= 0 && j < sLen && s[i] == s[j]) {
        res++;
        i--;
        j++;
    }
    return res;
}

int countSubstrings(char* s) {
    int sLen = strlen(s);
    int count = 0;
    for (int i = 0; i < sLen; i++) {
        // 单元素为核心
        count += checkSubStrings(s, sLen, i, i);
        // 双元素为核心
        count += checkSubStrings(s, sLen, i, i + 1);
    }
    return count;
}

[516] 最长回文子序列

题目描述

516 最长回文子序列

解题思路

前提：寻找最长回文子序列，子序列意味着元素可以不连续，元素相对顺序一致即可
思路：动态规划 dp[i][j]: 字符串在[i, j]中最长回文子序列的长度，分为两种情况，s[i] == s[j]时, dp[i][j] = dp[i+1][j-1] + 2；s[i] != s[j]时, 分别尝试将s[i]/s[j]加入,判断是否为回文子序列,取最大值, dp[i][j] = max(dp[i][j-1], dp[i+1][j])
重点：dp数组的定义、递推公式的推导、回文子串的条件判断

代码实现

C语言

动态规划

// 动态规划 dp[i][j]: 字符串在[i, j]中最长回文子序列的长度
// 分为两种情况
// s[i] == s[j]时, dp[i][j] = dp[i+1][j-1] + 2;
// s[i] != s[j]时, 分别尝试将s[i]/s[j]加入,判断是否为回文子序列,取最大值, dp[i][j] = max(dp[i][j-1], dp[i+1][j])

int maxFun(int p1, int p2)
{
    return p1 > p2 ? p1 : p2;
}

int longestPalindromeSubseq(char* s) {
    int sLen = strlen(s);
    int dp[sLen][sLen];
    // dp初始化
    for (int i = 0; i < sLen; i++) {
        for (int j = 0; j < sLen; j++) {
            dp[i][j] = 0;
        }
        dp[i][i] = 1;
    }
    // 遍历
    for (int i = sLen - 1; i >= 0; i--) {
        for (int j = i + 1; j < sLen; j++) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = maxFun(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][sLen - 1];
}