实现字符串反转

[metroluffy]

实现字符串反转

题目

实现一个字符串反转：输入：www.toutiao.com.cn 输出：cn.com.toutiao.www

要求：1.不使用字符串处理函数 2.空间复杂度尽可能小

实现

要实现字符串反转，应用双指针前后交换位置即可，这里需要注意字符串是基本类型，需要先转换成字符数组，反转后再拼接回去即可。

// 方法一, 不合题意，却可以大致整理出思路

function _swap(s) {
    return s.split('.').reverse().join('.')
}

// swap('www.toutiao.com.cn')
// "cn.com.toutiao.www"

// 分别实现上述函数

function split(s, op='') {
    let sa = [], ss = ''
    for(let si = 0; si < s.length; si++){
        if(s[si] === op){
            sa.push(ss);ss = ''
        } else {
            ss+= s[si]
        }
    }
    if(ss) sa.push(ss)
    return sa
}

function join(sa, op=',') {
    let s = '', l = 0
    while(l < sa.length) {
        s += sa[l] + (l == sa.length - 1 ? '' : op)
        l++
    }
    return s
}

function swap(s){
    if(!s) return ''
    s = split(s,'.')
    let i = 0, j = s.length - 1;
    while(i < j) {
        let t = s[i]
        s[i] = s[j]
        s[j] = t
        i++;
        j--;
    }
    return join(s, '.')
}

// swap('www.toutiao.com.cn')
// "cn.com.toutiao.www"

你也可以考虑在单次遍历中实现，空间复杂度应该差不多。

[Mrcxt]

用for循环是不是要比while好点，逻辑上也更清晰一点

[Mrcxt]

利用栈

String.prototype.str_reverse = function() {
        let stack = [],
            _str = '',
            str = this;

        for (let i = str.length - 1; i >= 0; i--) {
            let s = str[i]
            if (s === '.') {
                while (stack.length) {
                    _str += stack.pop();
                }
                _str += s
            } else {
                stack.push(s);
            }
        }

        while (stack.length) {
            _str += stack.pop();
        }

        return _str
    }

[metroluffy]

利用栈

String.prototype.str_reverse = function() {
        let stack = [],
            _str = '',
            str = this;

        for (let i = str.length - 1; i >= 0; i--) {
            let s = str[i]
            if (s === '.') {
                while (stack.length) {
                    _str += stack.pop();
                }
                _str += s
            } else {
                stack.push(s);
            }
        }

        while (stack.length) {
            _str += stack.pop();
        }

        return _str
    }

赞一个，不过在遇到 .之前是不是可以不用入栈

    for (let i = 0; i < str.length; i++) {
        let s = str[i]
        if (s === '.') {
            stack.push(_str);
            _str = ''
        } else {
            _str += s
        }
    }    

    while (stack.length) {
        _str += '.' + stack.pop();
    }

[Mrcxt]

利用栈

String.prototype.str_reverse = function() {
        let stack = [],
            _str = '',
            str = this;

        for (let i = str.length - 1; i >= 0; i--) {
            let s = str[i]
            if (s === '.') {
                while (stack.length) {
                    _str += stack.pop();
                }
                _str += s
            } else {
                stack.push(s);
            }
        }

        while (stack.length) {
            _str += stack.pop();
        }

        return _str
    }

赞一个，不过在遇到 .之前是不是可以不用入栈

    for (let i = 0; i < str.length; i++) {
        let s = str[i]
        if (s === '.') {
            stack.push(_str);
            _str = ''
        } else {
            _str += s
        }
    }    

    while (stack.length) {
        _str += '.' + stack.pop();
    }

good,第一版的split函数 ＋ 栈 😂

[KennethYo]

头条的面试是不能开辟额外空间

[pigpigever]

我记得字符串是不能被更改的？所以怎么样都会有额外空间吧，感觉这样写更简洁一点

function reverse(str) {
    let res = ''
    for (const word of str) {
        res = word + res
    }
    return res
}