题目:

给定一个字符串str和str的最长回文子序列strLPS,返回字符串str在任意位置添加最少字符后,整体都是回文串的其中一种结果。
例如:
str = “B1G2TY34I3OPX2S1″;
strLPS = “123I321″;
返回:B1GS2TYXPO34I43OPXYT2SG1B
注意:也可以返回B1SG2XPOTY34I43YTOPX2GS1B,总之返回一种满足条件的结果即可

 

解答:

难度:尉
在面试中本题可以很好的考察考生的代码实现的能力,如果str的长度为N,则时间复杂度可以做到O(N)。
首先,如果str的长度为N,strLPS的长度为M,则字符串str在任意位置添加最少字符后,整体都是回文串的长度应该是2*N-M。
本书给出的解法好似一个”剥洋葱”的过程,以题目给出的例子来说明:
str = “B1G2TY34I3OPX2S1″;
strLPS = “123I321″;
result = ….;
洋葱的第0层:
由strLPS中第0个和最后一个字符组成的,也就是”1…1″;
从str最左侧开始找字符’1′,发现’B’是str第0个字符,’1′是str第1个字符,所以左侧洋葱第0层外的部分为”B”,记为leftPart;
从str最右侧开始找字符’1′,发现’1′是str最后一个字符,所以右侧洋葱第0层外的部分为””,记为rightPart;
把(leftPart+rightPart的逆序)拷贝到result的左侧未设值的部分,把(rightPart+leftPart逆序)拷贝到result的右侧未设值的部分,则result为:”B…B”;
把洋葱的第0层拷贝到result的左侧未设值的部分和result的右侧未设值的部分,则result为”B1..1B”;
至此洋葱第0层被”剥掉”;
洋葱的第1层:
由strLPS中第1个和倒数第2个字符组成的,也就是”2…2″;
从str左侧的洋葱第0层往右找”2″,发现左侧洋葱第1层外的部分为”G”,记为leftPart;
从str右侧的洋葱第0层往左找”2″,发现右侧洋葱第1层外的部分为”S”,记为rightPart;
把(leftPart+rightPart的逆序)拷贝到result的左侧未设值的部分,把(rightPart+leftPart逆序)拷贝到result的右侧未设值的部分,则result为:”B1GS…SG1B”;
把洋葱的第1层拷贝到result的左侧未设值的部分和result的右侧未设值的部分,则result为”B1GS2…2SG1B”;
至此洋葱第1层被”剥掉”;
洋葱的第2层:
由strLPS中第2个和倒数第3个字符组成的,也就是”3…3″;
从str左侧的洋葱第1层往右找”3″,发现左侧洋葱第2层外的部分为”TY”,记为leftPart;
从str右侧的洋葱第1层往左找”3″,发现右侧洋葱第2层外的部分为”OPX”,记为rightPart;
把(leftPart+rightPart的逆序)拷贝到result的左侧未设值的部分,把(rightPart+leftPart逆序)拷贝到result的右侧未设值的部分,则result为:”B1GS2TYXPO…OPXYT2SG1B”;
把洋葱的第2层拷贝到result的左侧未设值的部分和result的右侧未设值的部分,则result为”B1GS2TYXPO3…3OPXYT2SG1B”;
至此洋葱第2层被”剥掉”;
洋葱的第i层:
由strLPS中第i个和第strLPS.length-1-i个字符组成;
从str左侧的洋葱第i-1层往右找strLPS[i],发现左侧洋葱第i层外的部分为leftPart;
从str右侧的洋葱第i-1层往左找strLPS[i],发现右侧洋葱第i层外的部分为rightPart;
把(leftPart+rightPart的逆序)拷贝到result的左侧未设值的部分,把(rightPart+leftPart逆序)拷贝到result的右侧未设值的部分;
把洋葱的第i层拷贝到result的左侧未设值的部分和result的右侧未设值的部分;

至此洋葱第i层被”剥掉”;


直到所有”洋葱”被剥掉,过程结束;
具体请参看如下代码中的generateASPByLPS方法。
代码:

 以下为测试用例:

 

欢迎留言