问题,求让指定字符串构成回文字符串的最小子串。

说明 回文字符串的特点是:自左->右读和自右->左读内容一致,譬如abcba
举例 给定字符串abc,让该字符串成为回文字符串可以拼接cba构成abccba成为回文,也可以拼接ba构成abcba成为回文,题目的要求是求最小回文,所以通过代码得到的最小子串应该为ba

解决方案1

思路 利用栈的结构来处理回文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function findMinCharsToPalindrome(strA) {
let str = [...strA].reverse().join("");
let stack = [];
let flag = false;
for (let i = 0, len = str.length; i < len; i++) {
if (stack[stack.length - 1] === str[i]) {
stack.pop()
flag = true;
console.log('推出', stack);
} else {
stack.push(str[i]);
console.log('入栈', stack);
}
}

let res = stack.join("");
return flag ? strA + res : strA + res.slice(1);
}

console.log("ab", findMinCharsToPalindrome("ab")); /* ab aba */
console.log("abc", findMinCharsToPalindrome("abc")); /* abc abcba */
console.log("abcc", findMinCharsToPalindrome("abcc")); /* abcc abccba */