算法：回文检测的学习引申
背景
回文检测是我在学习JavaScript的数组内容时接触到的一个比较典型的项目。
首先，我们来看看回文的定义：
若一个字符串等于将它反转后的结果，那可以称这个字符串是一个回文，常见的有：
● “ABA”
● “121”
● “上海自来水来自海上”等等等等
接下来通过3道题目来实现不同程度的回文检测。
题一
创建一个回文检测页面，支持用户输入文本后点击“Check”按钮可以判断输入的文本是不是回文，并输出判断结果。
解题思路：
1. 创建基础HTML（body节点需要包含至少输入框、检查按钮、结果输出框）；
2. 通过JS获取用户输入的值getValue
3. 将获取的值转化为数组 .split()
4. 将数组进行反转后得到新的数组 .reverse()
5. 将新数组转化为新的字符串 .join()
6. 判断新旧字符串是否相等，相等即为回文
7. 输出判断结果
示例代码：
//初始化变量
const userInput = document.getElementById("text-input");
const checkBtn = document.getElementById("check-btn");
const result = document.getElementById("result");
//设置判断逻辑
function isPalindrome(str){
const strReverse = str.toLowerCase().split('').reverse().join('');
return str.toLowerCase() == strReverse ? true : false;
}
//设置输出规则
const outputResult = (str) => {
if(str == ""){
alert("请先输入文本");
}else if(isPalindrome(str)){
result.innerText = `${str} 是一个回文。`
}else{
result.innerText = `${str} 不是回文。`
}
}
//为Check按钮设置点击事件侦听
checkBtn.addEventListener('click', () =>outputResult(userInput.value));
题二
在题一的基础上，对用户输入的值进行空格的过滤后再进行判断。
解题思路：
1. 在判断逻辑中使用.replace()方法将str中的空格替换为空串“”。
示例代码：
//初始化变量
const userInput = document.getElementById("text-input");
const checkBtn = document.getElementById("check-btn");
const result = document.getElementById("result");
//设置判断逻辑
function isPalindrome(str){
const strReverse = str.replace(/[\s]/g, "").toLowerCase().split('').reverse().join('');
return str.replace(/[\s]/g, "").toLowerCase() == strReverse ? true : false;
}
//设置输出规则
const outputResult = (str) => {
if(str == ""){
alert("请先输入文本");
}else if(isPalindrome(str)){
result.innerText = `${str} 是一个回文。`
}else{
result.innerText = `${str} 不是回文。`
}
}
//为Check按钮设置点击事件侦听
checkBtn.addEventListener('click', () =>outputResult(userInput.value));
题三
除了要检测字符串是不是一个回文外，还需要检测它有多少个回文子串。
子串：从字符串中任意截取的部分均是字符串的子串，若子串满足回文定义，则认为该子串是回文子串。
解题思路：
1. 暴力穷举法
2. 构造获取给定str中的所有子串的函数
a. 将str转化为数组 .split()方法
b. 捕获所有的子串.slice()方法
c. 将捕获的子串推入新数组 .push()方法
3. 循环为新数组的元素转化为字符串后调用判断逻辑
4. 输出字符串本身是否回文串，以及其回文子串的个数
示例代码：
//初始化变量
const userInput = document.getElementById("text-input");
const checkBtn = document.getElementById("check-btn");
const result = document.getElementById("result");
//设置判断逻辑
function isPalindrome(str){
const strReverse = str.replace(/[\s]/g, "").toLowerCase().split('').reverse().join('');
return str.replace(/[\s]/g, "").toLowerCase() == strReverse ? true : false;
}
//获取回文子串个数
const countPalindromeSubstrings = (str) =>{
//设置捕获条件变量
const arr = str.split("");
const n = arr.length;
const Substrs = [];
//设置捕获逻辑
for(let start = 0; start < n; start++){
for(let indexEnd = start; indexEnd < n; indexEnd++){
const Substr = arr.slice(start, indexEnd + 1).join();
Substrs.push(Substr);
}
}
//判断回文子串个数方法
let count = 0 ;
for(let i = 0; i < Substrs.length; i++){
if(isPalindrome(Substrs[i])){
count++;
}
}
return count;
}
//设置输出规则
const outputResult = (str) => {
if(str == ""){
alert("请先输入文本");
}else if(isPalindrome(str)){
result.innerText = `${str} 是一个回文。其回文子串有${countPalindromeSubstrings(str)}个。`
}else{
result.innerText = `${str} 不是回文。其回文子串有${countPalindromeSubstrings(str)}个。`
}
}
//为Check按钮设置点击事件侦听
checkBtn.addEventListener('click', () =>outputResult(userInput.value));
拓展
通过以上三道题，对字符串、数组的常见方法、基础的正则用法、以及基础的循环语句（for循环）、条件语句（if语句）均有了初步的认知。
在解决回文检测的过程中，我们还可以做更多的引申，包括：
1. 如果不用暴力穷举法，而基于回文本身的左右对称性质来计算回文子串的个数。
2. 如果修改子串的定义为不要求连续，任意组合都可以得到子串，又该如何计算。
3. 如果子串中的重复项要排除掉，又有哪几种方式处理呢。
评论
发表评论