JavaScript算法练习: JavaScript中回文(Palindromes)处理

Palindromes称之为回文。在中文文当中是指倒着念和顺着念都是相同的,前后对称,例如“上海自来水来自海上”。在英文文当中是指正着看和反着看都相同的单词,例如“madam”。而对于数字,又称之为回文数,是指一个像“16461”这样的对称的数,即这个数的数字按相反的顺序重新排列后得到的数和原来的数一样。

在JavaScript中Palindromes也常出现在一些算法题中,这篇文章主要介绍如何使用JavaScript判断一个字符是不是Palindromes。

算法

  • 判断给定的字符串,如果字符串是一个Palindromes,那么返回true,反之返回false
  • Palindromes是一个词或一个名子,在忽略标点符号和间距之下,前后指写方式相同

测试用例

  • palindrome(“race car”)返回true
  • palindrome(“not a palindrome”)返回false
  • palindrome(“A man, a plan, a canal. Panama”)返回true
  • palindrome(“never odd or even”)返回true
  • palindrome(“nope”)返回false
  • palindrome(“almostomla”)返回false
  • palindrome(“My age is 0, 0 si ega ym.”)返回true
  • palindrome(“1 eye for of 1 eye.”)返回false
  • palindrome(“0_0 (: /- 🙂 0–0”)返回true
  • palindrome(“我爱妈妈,妈妈爱我”)返回true

其中palindrome()是一个我们将要定义的函数,并且给这个函数传入一个str参数,如果str是一个Palindromes,将返回的是true,反之返回的是false

知识点

在后面的介绍中,将会用到的一些JavaScript知识点:

需要用到的正则表达式

正则表达式是被用来匹配字符串中的字符组合的模式。在JavaScript中,正则表达式也是对象。这种模式可以被用于 RegExp 的 exec 和 test 方法以及 String 的 match、replace、search 和 split 方法。

当你需要搜索一个比直接匹配需要更多条件的匹配时,比如寻找一个或多个b's,或者寻找空格,那么这时模式将要包含特殊字符。

在这篇文章中主要用到下面两个正则表达式:

/[^A-Za-z0–9]/g
// 或

/[W_]/g

W删除所有非常字母数字字符:

  • W匹配一个非单字字符
  • 等价于[^A-Za-z0-9_]

那么W的意思就是:

  • [^A-Z]匹配非26个大写字母中的任意一个
  • [^a-z]匹配非26个小写字母中的任意一个
  • [^0-9]匹配非0到9中的任意一个数字
  • [^_]匹配非下划线

因为我们测试用例中的最后一个palindrome(“0_0 (: /- 🙂 0–0”)将返回的是true,也就是说_(: /- :)–必须是相匹配的。所以需要添加_这个符号来通过这个特定的测试用例。

最后还需要添加g,表示全局搜索。我们最后需要的正则表达式是/[W_]/g

实现方法

检测一个字符串是不是Palindrome,方法不仅仅是一种,接下来看看网上介绍的几种方法:

方法一

function palindrome(str) {
    var re = /[W_]/g; // 或者 var re = /[^A-Za-z0-9]/g;

    var lowRegStr = str.toLowerCase().replace(re,'');

    var reverseStr = lowRegStr.split('').reverse().join('');

    return reverseStr === lowRegStr;
}

也可以写成:

function palindrome(str) {
  return str.replace(/[W_]/g, '').toLowerCase() ===
         str.replace(/[W_]/g, '').toLowerCase().split('').reverse().join('');
}

这个方案,我们使用了下面几个方法:

  • 通过正则表达式/[W_]/g(或者/[^A-Za-z0-9]/g)删除不必要的字符
  • 通过toLowerCase()方法将传入的字符串str转换为小写字母。比如toLowerCase(),当str的值为”A man, a plan, a canal. Panama”时,str.toLowerCase()就相当于”A man, a plan, a canal. Panama”.toLowerCase(),其值将是”a man, a plan, a canal. panama”
  • 通过replace()方法和前面定义好的正则表达式/[W_]/g匹配出需要的字符(删除不必要的字符)。比如上例中replace(/[W_]/g, ”)就相当于”a man, a plan, a canal. panama”.replace(/[W_]/g, ”),得到的值将是”amanaplanacanalpanama”
  • 通过split()方法将字符串转换成数组。如”amanaplanacanalpanama”.split(”),得到的值[“a”, “m”, “a”, “n”, “a”, “p”, “l”, “a”, “n”, “a”, “c”, “a”, “n”, “a”, “l”, “p”, “a”, “n”, “a”, “m”, “a”]
  • 使用reverse()方法将数组做一个反转处理[“a”, “m”, “a”, “n”, “a”, “p”, “l”, “a”, “n”, “a”, “c”, “a”, “n”, “a”, “l”, “p”, “a”, “n”, “a”, “m”, “a”].reverse,此时得到一个新数组[“a”, “m”, “a”, “n”, “a”, “p”, “l”, “a”, “n”, “a”, “c”, “a”, “n”, “a”, “l”, “p”, “a”, “n”, “a”, “m”, “a”]
  • 通过join()方法,将得到的新数组的每个数组项连接在一起变成一个新的字符串,如[“a”, “m”, “a”, “n”, “a”, “p”, “l”, “a”, “n”, “a”, “c”, “a”, “n”, “a”, “l”, “p”, “a”, “n”, “a”, “m”, “a”].join(”),其值将变成一个新字符串”amanaplanacanalpanama”

通过上面的几个方法,我们得到两个不同的字符串,其中第一个是str.replace(/[W_]/g, '').toLowerCase(),可以将这个字符串赋值给一个变量,比如lowRegStr,另外一个是经过处理后得到一个反转字符串str.replace(/[W_]/g, '').toLowerCase().split('').reverse().join(''),同样可以将其赋值给一个变量reverseStr,最后给这两个值做全等比较lowRegStr === reverseStr,如果他们全等,返回的是true,也就是说字符串str是一个真正的Palindromes,反之返回的将是false,那么字符串str就不是一个Palindromes。

JavaScript中回文(Palindromes)处理

方法二

这个方法是使用for循环来处理的。

function palindrome (str) {
    var re = /[W_]/g;
    var lowRegStr = str.toLowerCase().replace(re, '');
    var len = lowRegStr.length;

    for (var i = 0, halfLen = len / 2; i < halfLen; i++){
        if (lowRegStr[i] !== lowRegStr[len - 1 - i]) {
            return false;
        }
    }
    return true;
}

这个方法主要分为以下几个步骤:

  • 通过正则表达式,删除字符串中不必要的字符,并且将字符串转换成小写字符
  • 创建一个for循环,同时声明一个变量halfLen,其值是字符串长度的一半len / 2,并且将其当作循环的终点值
  • 判断lowRegStr[i]和lowRegStr[len – 1 – i]是否相同,如果不相同,返回false,反之返回true

假设str的值为"A man, a plan, a canal. Panama",其length值为30, 对应的len / 2 = 15。下面,通过下表来看看整个遍历中,lowRegStr[i]lowRegStr[len - 1 - i]对应的值:

遍历的次数i = ?i < len / 2i++lowRegStr[i]lowRegStr[len - 1 - i]if(lowRegStr[i] !== lowRegStr[len - 1 - i])
第一次遍历0yes1lowRegStr[0] = "a"lowRegStr[15 - 1 - 0] = "a"false
第二次遍历1yes2lowRegStr[1] = "m"lowRegStr[15 - 1 - 1] = "m"false
第三次遍历2yes3lowRegStr[2] = "a"lowRegStr[15 - 1 - 2] = "a"false
第四次遍历3yes4lowRegStr[3] = "n"lowRegStr[15 - 1 - 3] = "n"false
第五次遍历4yes5lowRegStr[4] = "a"lowRegStr[15 - 1 - 4] = "a"false
第六次遍历5yes6lowRegStr[5] = "p"lowRegStr[15 - 1 - 5] = "p"false
第七次遍历6yes7lowRegStr[6] = "l"lowRegStr[15 - 1 - 6] = "l"false
第八次遍历7yes8lowRegStr[7] = "a"lowRegStr[15 - 1 - 7] = "a"false
第九次遍历8yes9lowRegStr[8] = "n"lowRegStr[15 - 1 - 8] = "n"false
第十次遍历9yes10lowRegStr[9] = "a"lowRegStr[15 - 1 - 9] = "a"false
第十一次遍历10yes11lowRegStr[10] = "c"lowRegStr[15 - 1 - 10] = "c"false
第十二次遍历11yes12lowRegStr[11] = "a"lowRegStr[15 - 1 - 11] = "a"false
第十三次遍历12yes13lowRegStr[12] = "n"lowRegStr[15 - 1 - 12] = "n"false
第十四次遍历13yes14lowRegStr[13] = "a"lowRegStr[15 - 1 - 13] = "a"false
第十五次遍历14yes15lowRegStr[14] = "l"lowRegStr[15 - 1 - 14] = "l"false
第十六次遍历15no

JavaScript中回文(Palindromes)处理

方法三

function palindrome (str) {
    // 删除字符串中不必要的字符
    var re = /[W_]/g;
    // 将字符串变成小写字符
    var lowRegStr = str.toLowerCase().replace(re, '');
    // 如果字符串lowRegStr的length长度为0时,字符串即是palindrome
    if (lowRegStr.length === 0) {
        return true;
    }

    // 如果字符串的第一个和最后一个字符不相同,那么字符串就不是palindrome
    if (lowRegStr[0] !== lowRegStr[lowRegStr.length - 1]) {
        return false;
    } else {
        return palindrome(lowRegStr.slice(1, lowRegStr.length - 1));
    }
}

方法四

function palindrome (str) {
    // 删除字符串中不必要的字符
    var re = /[W_]/g;
    // 将字符串变成小写字符
    var lowRegStr = str.toLowerCase().replace(re, '');
    var count = 0;
    // 检查字符串是不是空字符串
    if (lowRegStr === "") {
        return false;
    }
    // 检查字符串长度是单数还是双数
    if (lowRegStr.length % 2 === 0) {
        count = lowRegStr.length / 2;
    } else {
        // 如果字符串长度值等于1,那么它是palindrome
        if (lowRegStr.length === 1) {
            return true;
        } else {
            // 如果字符串长度是奇数,忽略字符串中最中间的字符
            count = (lowRegStr.length - 1) / 2;
        }
    }
    // 添加for循环,遍历字符串,检测字符串第一个字符和最后一个字符,然后依次类推
    for (var i = 0; i < count; i++) {
        // 如果不匹配字符串就不是一个palindrome
        if (lowRegStr[i] != lowRegStr.slice(-1 - i)[0]) {
            return false;
        }
    }
    return true;
}

不过这种方法测试过之后,检测中文类型的回文不生效,比如palindrome(“我爱妈妈,妈妈爱我”)返回false。

总结

文中通过不同的方法简单阐述了JavaScript中如何检测一个字符串是不是一个回文。这也是JavaScript中算法练习之一。文章中主要运用到了JavaScript中的正则表达式,toLowerCase()split()reverse()join()等基础知识。如果您在这方面有更好的方案,欢迎在下面的评论中分享。

扩展阅读

原文链接:https://www.w3cplus.com/javascript/palindrome-check-in-javascript.html

发表评论

登录后才能评论