JavaScript算法练习:字符串反转

今天在freeCodeCamp上面刷题,碰到一题是有关于字符串反转。反转一个字符串是JavaScript中常见的面试题之一。可能面试官会给你一个字符串“Hello Word!”,让你通过JavaScript的方法,将其变成”!droW olleH”。

我也是初学者,利用前面所学数组相关的知识以及题目的提示,我算是过关了,后来想,是不是还有其他的方法能破此题呢?搜索了一下,还是有不少的方法,这里把这些方法罗列一下,以备后面可以使用。

要做的事情

我们要做的事情:

  • 将提供的字符串反向显示
  • 在反向字符串之前,需要将字符串转化成一个数组
  • 最终结果依旧是一个字符串

接下来,我们一起看看有哪些方法能实现上述要求。

使用内置函数

在练习题中,提示我们可以使用三种方法配合,能顺利让一个字符串反向显示:

  • prototype.split()
  • prototype.reverse()
  • prototype.join()

简单的过一下:

  • split()方法将一个字符串对象的每个字符拆出来,并且将每个字符串当成数组的每个元素
  • reverse()方法用来改变数组,将数组中的元素倒个序排列,第一个数组元素成为最后一个,最后一个变成第一个
  • join()方法将数组中的所有元素边接成一个字符串

来看个实例:

function reverseString(str) {
    // 第一步,使用split()方法,返回一个新数组
    // var splitString = "hello".split("");

    var splitString = str.split(""); //将字符串拆分

    // 返回一个新数组["h", "e", "l", "l", "o"]

    // 第二步,使用reverse()方法创建一个新数组
    // var reverseArray = ["h", "e", "l", "l", "o"].reverse();

    var reverseArray = splitString.reverse(); 
    // 原数组元素顺序反转["o", "l", "l", "e", "h"]

    // 第三步,使用join()方法将数组的每个元素连接在一起,组合成一个新字符串
    // var joinArray = ["o", "l", "l", "e", "h"].join("");

    var joinArray = reverseArray.join(""); 
    // "olleh"

    // 第四步,返回一个反转的新字符串
    return joinArray; // "olleh"
}

reverseString("hello"); // => olleh

将上面的方法简化一下,可以写成这样:

function reverseString(str) {
    return str.split("").reverse().join("");
}
reverseString("hello"); // => olleh

使用一个递减循环遍历将字符串反转

这种方法使用的是一个for循环给原字符串做一个递减遍历,然后将遍历的字符串重新合并成一个新字符串:

function reverseString(str) {
    // 第一步:创建一个空的字符串用来存储新创建的字符串

    var newString = "";

    // 第二步:使用for循环
    // 循环从str.length-1开始做递减遍历,直到 i 大于或等于0,循环将继续
    // str.length - 1对应的就是字符串最后一个字符o

    for (var i = str.length - 1; i >= 0; i--) { 
        newString += str[i]; // 或者 newString = newString + str[i];
    }

    // 第三步:返回反转的字符串
    return newString; 
}

reverseString('hello'); // => // "olleh"

简单的看看字符串遍历的过程。假设需要将字符串”hello”反转。其整个遍历过程如下表所示:

迭代顺序对应i的值新字符串 newString
每次迭代str.length – 1newString + str[i]
第一次迭代5 – 1 = 4“” + “o” = “o”
第二次迭代4 – 1 = 3“o” + “l” = “ol”
第三次迭代3 – 1 = 2“ol” + “l” = “oll”
第四次迭代2 – 1 = 1“oll” + “e” = “olle”
第五次迭代1 – 1 = 0“olle” + “h” = “olleh”

其实上面的for循环,也可以换成while循环:

function reverseString (str) {
    var newString = '';
    var i = str.length;

    while (i > 0) {
        newString += str.substring(i - 1, i);
        i--;
    }

    return newString;
}

reverseString("hello"); // => olleh

在while循环中substring()方法。substring() 返回字符串两个索引之间(或到字符串末尾)的子串。

使用递归实现字符串反向

使用String.prototype.substr()String.prototype.charAt()方法也可以将一个字符串反向。

substr() 方法返回字符串中从指定位置开始到指定长度的子字符串。比如:

var str = "abcdefghij";

console.log("(1,2): "    + str.substr(1,2));   // (1,2): bc
console.log("(-3,2): "   + str.substr(-3,2));  // (-3,2): hi
console.log("(-3): "     + str.substr(-3));    // (-3): hij
console.log("(1): "      + str.substr(1));     // (1): bcdefghij
console.log("(-20, 2): " + str.substr(-20,2)); // (-20, 2): ab
console.log("(20, 2): "  + str.substr(20,2));  // (20, 2):

charAt() 方法返回字符串中指定位置的字符。字符串中的字符从左向右索引,第一个字符的索引值为 0,最后一个字符(假设该字符位于字符串 stringName 中)的索引值为 stringName.length - 1。 如果指定的 index 值超出了该范围,则返回一个空字符串。

var anyString = "Brave new world";
console.log("The character at index 0   is '" + anyString.charAt(0)   + "'"); // =>The character at index 0 is 'B'
console.log("The character at index 1   is '" + anyString.charAt(1)   + "'"); // =>The character at index 1 is 'r'
console.log("The character at index 2   is '" + anyString.charAt(2)   + "'"); // =>The character at index 2 is 'a'
console.log("The character at index 3   is '" + anyString.charAt(3)   + "'"); // => The character at index 3 is 'v'
console.log("The character at index 4   is '" + anyString.charAt(4)   + "'"); // => The character at index 4 is 'e'
console.log("The character at index 999 is '" + anyString.charAt(999) + "'"); // => The character at index 999 is ''

结合起来,我们可以这样做实现字符串反向:

function reverseString(str) {
    if (str === "") {
        return "";
    } else {
        return reverseString(str.substr(1)) + str.charAt(0);
    }
}
reverseString("hello"); // => olleh

第一部分的递归方法。你需要记住,你不会只调用一次,你将会有几个嵌套的调用。

每次调用str === “?”reverseString(str.subst(1))+ str.charAt(0)
第一次调用reverseString(“Hello”)reverseString(“ello”) + “h”
第二次调用reverseString(“ello”)reverseString(“llo”) + “e”
第三次调用reverseString(“llo”)reverseString(“lo”) + “l”
第四次调用reverseString(“lo”)reverseString(“o”) + “l”
第五次调用reverseString(“o”)reverseString(“”) + “o”

第二部分的递归方法。

每次调用返回
第五次调用reverseString(“”) + “o” = “o”
第四次调用reverseString(“o”) + “l” = “o” + “l”
第三次调用reverseString(“lo”) + “l” = “o” + “l” + “l”
第二次调用reverserString(“llo”) + “e” = “o” + “l” + “l” + “e”
第一次调用reverserString(“ello”) + “h” = “o” + “l” + “l” + “e” + “h”

上面的方法还可以继续改良一下,改成三元操作符:

function reverseString(str) {
    return (str === '') ? '' : reverseString(str.substr(1)) + str.charAt(0);
}
reverseString("hello"); // => olleh

还可以换成这样的方式

function reverseString(str) {
  return str && reverseString(str.substr(1)) + str[0];
}
reverseString("hello"); // => olleh

其他方法

除了上面的方法之外,其实还有其他一些方法:

方法一

function reverseString (str) {
    var newString = [];
    for (var i = str.length - 1, j = 0; i >= 0; i--, j++) {
        newString[j] = str[i];
    }
    return newString.join('');
}

reverseString("hello"); // => olleh

方法二

function reverseString (str) {
    for (var i = str.length - 1, newString = ''; i >= 0; newString += str[i--] ) {

    }
    return newString;
}

reverseString("hello"); // => olleh

方法三

function reverseString (str) {
    function rev(str, len, newString) {
        return (len === 0) ? newString : rev(str, --len, (newString += str[len]));
    }
    return rev(str, str.length, '');
}
reverseString("hello"); // =>olleh

方法四

function reverseString (str) {
    str = str.split('');
    var len = str.length,
        halfIndex = Math.floor(len / 2) - 1,
        newString;
    for (var i = 0; i <= halfIndex; i++) {
        newString = str[len - i - 1];
        str[len - i - 1] = str[i];
        str[i] = newString;
    }
    return str.join('');
}
reverseString("hello"); // => olleh

方法五

function reverseString (str) {
    if (str.length < 2) {
        return str;
    }
    var halfIndex = Math.ceil(str.length / 2);
    return reverseString(str.substr(halfIndex)) + reverseString(str.substr(0, halfIndex));
}

reverseString("hello"); // =>olleh

方法六

function reverseString(str) {
  return [].reduceRight.call(str, function(prev, curr) {
    return prev + curr;
  }, '');
}

reverseString("hello"); // =>olleh

ES6的方法

在ES6中,可以变得更为简单一些,如:

[...str].reverse().join('');

或者:

[...str].reduceRight( (prev, curr) => prev + curr );

或者:

const reverse = str =>
  str && reverse(str.substr(1)) + str[0];

结论

字符串反转是一个小而简单的算法,前面也说了,常被用来面试JavaScript基础。你可以使用上面各种方法来解决这个问题,甚至使用更为复杂的解决方案。如果你有更好的方法,欢迎在下面的评论中补上,与我们一起分享。

参考资料

初学者学习笔记,如有不对,还希望高手指点。如有造成误解,还希望多多谅解。

原文链接:https://www.w3cplus.com/javascript/how-to-reverse-a-string-in-javascript-in-different-ways.html

发表评论

登录后才能评论