前言:
现时大家对“正则表达式 回文”可能比较讲究,咱们都想要知道一些“正则表达式 回文”的相关内容。那么小编同时在网络上搜集了一些有关“正则表达式 回文””的相关知识,希望大家能喜欢,咱们一起来了解一下吧!125. 验证回文串题目描述(难度:简单)给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。说明:本题中,我们将空字符串定义为有效的回文串。示例1:
输入: "A man, a plan, a canal: Panama" 输出: true示例2:
输入: "race a car" 输出: false思路1:去除字符串中的非字符和非数字,然后转成数组,反转。将原字符和新字符比较,看是否相等1.将传入的字符串,利用 toLowerCase() 方法统一转化为小写,再利用正则表达式 /[ ^ A-Za-z0-9]/g 在字符串中去除非字母和数字,得到字符串 arr。2.将字符串 arr 转换为数组,利用数组的方法反转数组,再将数组转为字符串 newArr。3.将字符串 arr 和 字符串 newArr 进行比较,相等即为回文串,不相等则不为回文串。代码1
/** * @param {string} s * @return {boolean} */ const isPalindrome = (s) => { const newStr = s.toLowerCase().replace(/[^a-zA-Z0-9]/g,''); const arr = newStr.split('').reverse().join(''); return newStr === arr; };复杂度分析1时间复杂度:O(n)该解法中,toLowerCase(), replace(), split(), reverse(), join() 的时间复杂度都为 ,且都在独立的循环中执行,因此,总的时间复杂度依然为O(n) 。空间复杂度:O(n)该解法中,申请了 1 个大小为 的字符串和 1 个大小为 的数组空间,因此,空间复杂度为 ,即 O(n)。思路2:首先,去除字符串中的非字母和数字,再将字符串转换为数组,再对数组首尾一一比较,即可得出结果。代码2
/** * @param {string} * @return {boolean} */ const isPalindrome = (s) => { // 将传入的字符串,统一转化为小写,同时去除非字母和数字,在转换为数组 const arr = s.toLowerCase().replace(/[^A-Za-z0-9]/g, '').split(''); let i = 0; let j = arr.length - 1; // 循环比较元素 while (i < j) { // 从首尾开始, 一一比较元素是否相等 if (arr[i] === arr[j]) { // 若相等,即第二个元素和倒数第二个元素继续比较,依次类推 i += 1; j -= 1; } else { // 只要有一个相对位置上不相等,既不是回文串 return false; } } // 是回文串 return true; };复杂度分析2时间复杂度:O(n)该解法中 while 循环最多执行 n/2n/2 次,即回文时,因此,时间复杂度为 O(n)空间复杂度:O(n)O(n) 该解法中,申请了 1 个大小为 nn 的数组空间,因此,空间复杂度为 O(n)
如果文章对您有帮助,欢迎关注和转发,让更多的人看到,一起传递知识。
版权声明:
本站文章均来自互联网搜集,如有侵犯您的权益,请联系我们删除,谢谢。
标签: #正则表达式 回文