《灵珠觉醒:从零到算法金仙的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)