问题1:检查给定的字符串是否是回文字符串。

说明 回文字符串的特点是:自左->右读和自右->左读内容一致,譬如上海自来水来自海上

解决方案1
1
2
3
4
5
6
7
8
9
10
11
12
/* 思路 : 使用数组来进行处理*/
/* (1) 先把字符串转换为数组,然后倒序后再处理为字符串 */
/* (2) 比较两个字符串是否全等,全等则表示该字符串是回文 */
function isPalindrome(str) {
let target = [...str].reverse().join("");
return target === str;
}

/* 测试数据 */
console.log(isPalindrome("aba")); /* true */
console.log(isPalindrome("abc")); /* false */
console.log(isPalindrome("上海自来水来自海上")); /* true */
解决方案2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/* 思路 : 使用栈数据结构进行处理 */
/* (1) 利用栈结构通过入栈和出栈的操作来完成字符串的翻转 */
/* (2) 比较两个字符串是否全等,全等则表示该字符串是回文 */
class Stack {
constructor() {
this.top = 0;
this.data = [];
}
pop() {
this.top--;
return this.data.pop();
}
push(ele) {
this.data[this.top++] = ele;
}
peek() {
return this.data[this.top - 1];
}
clear() {
this.top = 0;
this.data = [];
}
length() {
return this.top;
}
}

function isPalindrome(str) {
let stack = new Stack();
for (let i = 0; i < str.length; i++) {
stack.push(str[i]);
}
let target = "";
while (stack.length() > 0) {
target += stack.pop();
}
return str === target;
}

let str1 = "abcdcba";
let str2 = "abcaba";
let str3 = "上海自来水来自海上";
console.log(`"${str1}"${isPalindrome(str1) ? "是" : "不是"}回文字符串。`);
console.log(`"${str2}"${isPalindrome(str2) ? "是" : "不是"}回文字符串。`);
console.log(`"${str3}"${isPalindrome(str3) ? "是" : "不是"}回文字符串。`);

/* 执行结果 */
// wendingding$ node 02-检查回文.js
// "abcdcba"是回文字符串。
// "abcaba"不是回文字符串。
// "上海自来水来自海上"是回文字符串。
问题2:请编写函数求字符串中存在的最长回文字符串。

说明 譬如给定字符串为1abcba123,那么该该字符串中存在的最长回文字符串应该为1abcba1

解决方案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
function longestPalindrome(str) {
/* 如果字符串为空或者只有一个字符,那么就直接返回当前字符 */
if (str.length <= 1) return str;

let chars = [],offset, k;
/* 通过循环把所有的字符(可能存在最长回文都添加到chars中) */
for (var i = 0; i < str.length; i += 1) {
offset = k = 0;
while (str[i+ offset] && str[i - offset] && str[i-offset] === str[i+offset]) {
offset++;
};
chars.push(str.slice(i - offset + 1, i + offset))

console.log(`[${chars.toString()}]`);
while (str[i + 1 + k] && str[i - k] && str[i + 1 + k] === str[i - k]) {
k++;
}
chars.push(str.slice(i - k + 1, i + k + 1))
}
/* 对数组中的字符串按照长度进行排序(长->短) */
let result = chars.sort((a, b) => {
return b.length - a.length
});
console.log(`排序后的数组:[${result.join(",")}]`);
return result[0];
};

/* 测试数据 */
console.log(longestPalindrome("ac121ca123210"));
/* 打印显示 */
/*
[a]
[a,,c]
[a,,c,,1]
[a,,c,,1,,ac121ca]
[a,,c,,1,,ac121ca,,1]
[a,,c,,1,,ac121ca,,1,,c]
[a,,c,,1,,ac121ca,,1,,c,,a]
[a,,c,,1,,ac121ca,,1,,c,,a,,1]
[a,,c,,1,,ac121ca,,1,,c,,a,,1,,2]
[a,,c,,1,,ac121ca,,1,,c,,a,,1,,2,,12321]
[a,,c,,1,,ac121ca,,1,,c,,a,,1,,2,,12321,,2]
[a,,c,,1,,ac121ca,,1,,c,,a,,1,,2,,12321,,2,,1]
[a,,c,,1,,ac121ca,,1,,c,,a,,1,,2,,12321,,2,,1,,0]
排序后的数组:[ac121ca,12321,a,a,1,c,c,1,2,1,2,1,0,,,,,,,,,,,,,]
ac121ca */
在上面的代码中,可能会存在拥有多个最长回文子串(譬如传入的字符串是abccba1221a)或者没有回文子串(譬如传入的字符串是 abc)的情况,因此还需要调整下代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
function longestPalindrome(str) {
if (str.length <= 1) return str;

let chars = [];
let offset, k;
for (var i = 0; i < str.length; i += 1) {
offset = k = 0;
while (str[i + offset] && str[i - offset] && str[i-offset] === str[i+offset]) {
offset++;
};

chars.push(str.slice(i - offset + 1, i + offset));
while (str[i + 1 + k] && str[i - k] && str[i + 1 + k] === str[i - k]) {
k++;
}
chars.push(str.slice(i - k + 1, i + k + 1))
}

let result = chars.sort((a, b) => {
return b.length - a.length
});
console.log(`排序后的数组:[${result.join(",")}]`);

/* 注意:特殊情况的处理 */
let maxLength = result[0].length;
let allPalindromes = [];
result.forEach(item => {
if (maxLength == item.length) allPalindromes.push(item);
});

return maxLength == 1 ? `抱歉,在该字符串中没有找到回文子串` :
`列出字符串中的最长回文子串为:${allPalindromes.join(" 和 ")}`;
};

/* 测试数据 */
console.log(longestPalindrome("abc"));
console.log(longestPalindrome("ac121ca123210"));
console.log(longestPalindrome("abccba1221a"));

/* 打印结果 */
// wendingding$ node 02-min.js
// 排序后的数组:[a,b,c,,,]
// 抱歉,在该字符串中没有找到回文子串
// 排序后的数组:[ac121ca,12321,a,a,1,c,c,1,2,1,2,1,0,,,,,,,,,,,,,]
// 列出字符串中的最长回文子串为:ac121ca
// 排序后的数组:[abccba,a1221a,a,a,c,b,b,1,2,c,2,1,a,,,,,,,,,]
// 列出字符串中的最长回文子串为:abccba 和 a1221a