双端队列检测一个词组是否构成回文
date
Mar 13, 2023
slug
js-two-ended-queue-palindrome
status
Published
tags
JavaScript数据结构与算法
Queue
JavaScript
summary
Apply palindrome with two-ended-queue
type
Post
回文是正反都能读通的单词、词组、数或一系列字符的序列。判断一个词组或字符串是否为回文最简单的方法是将字符串反向排列并检查它和原字符串是否相同。如果两者相同,那么它就是一个回文。
class Deque{
constructor(){
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
addBack(element){
this.items[this.count] = element;
this.count++;
}
isEmpty(){
return this.count - this.lowestCount === 0;
}
size(){
return this.count - this.lowestCount;
}
removeFront(){
if(this.isEmpty()){
return undefined;
}
const re = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount ++;
return re;
}
removeBack(){
if(this.isEmpty()){
return undefined;
}
this.count --;
const res = this.items[this.count];
delete this.items[this.count];
return res;
}
}
function palindromeChecker(aString){
if(aString === undefined || aString === null || (aString !==null && aString.length==0)){
//检查传入的字符串参数是否合法
return false;
}
const deque = new Deque();
//将所有字母转换为小写并移除空格
const lowerString = aString.toLocaleLowerCase().split(' ').join('');
let isEqual = true;
let firstChar,lastChar;
for(let i = 0; i < lowerString.length; i++){
//将lowerString中的字符逐个加入队列中
deque.addBack(lowerString.charAt(i));
}
while(deque.size() > 1 && isEqual){//所有双端队列中元素大于1(一个字符为回文)并且首尾字符相同
firstChar = deque.removeFront();//从前端移除一个元素
lastChar = deque.removeBack();//从后端移除一个元素
//移除的两个字符必须相同
if(firstChar !== lastChar){
isEqual = false;
}
}
return isEqual;
}
console.log('level', palindromeChecker('level'));
以下测试结果全为 true
console.log('a', palindromeChecker('a'));
console.log('aa', palindromeChecker('aa'));
console.log('kayak', palindromeChecker('kayak'));
console.log('level', palindromeChecker('level'));
console.log('Was it a car or a cat I saw', palindromeChecker('Was it a car
or a cat I saw'));
console.log('Step on no pets', palindromeChecker('Step on no pets'));