《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(37)诛仙四剑破子串 - 最长公共子序列(LCS)

时间:2025-03-15 16:48:53

《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(37)诛仙四剑破子串 - 最长公共子序列(LCS)

哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的诛仙剑林,林中有一座巨大的诛仙四剑阵,剑身闪烁着神秘的光芒。剑阵入口处有一块巨大的石碑,上面刻着一行文字:“欲破此阵,需以诛仙四剑之力,破子串,LCS显真身。”

哪吒定睛一看,石碑上还有一行小字:“字符串"abcde""ace"的最长公共子序列为"ace",长度为3。”哪吒心中一动,他知道这是一道关于最长公共子序列(LCS)的难题,需要通过动态规划的方法,找到两个字符串的最长公共子序列。


暴力解法:诛仙四剑的初次尝试

哪吒心想:“要找到最长公共子序列,我可以逐个字符比较。”他催动诛仙四剑之力,从两个字符串的开头开始,逐个字符比较,试图找到最长的公共子序列。

int longestCommonSubsequence(string text1, string text2) {
   
    if (text1.empty() || text2.empty()) return 0;
    if (text1[0] == text2[0]) {
   
        return 1 + longestCommonSubsequence(text1.substr(1)