# 557. Reverse Words in a String III

Array 直接抓值一定比 unshift 快 / 寫到兩個 for 可能就要考慮是否有更好解法了

LeetCode

Given a string, you need to reverse the order of characters in each word 
within a sentence while still preserving whitespace and initial word order.

input: string
output: 每個單字都要被反轉，中間不能有空格

Example 1:
Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Note: In the string, each word is separated by single space and there will not be any extra space in the string.

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {}

怎麼解

1. 這題用了 Stack 方式想，效能很差

var reverseWords = function(s) {
    let stack = [];
    let result = [];
    for(let i = 0; i < s.length; i++){
        if(s.charAt(i) !== ' '){
            stack.push(s.charAt(i))
        }else{
            getStack()
            result.push(' ')
        }
        
    }
    getStack()
    

    function getStack(){
        let ind = 0;
        let len = stack.length;
        while(ind < len){
            result.push(stack.pop());
            ind ++;
        }
        
        stack = []
    }

    return result.join('');
};

console.log(reverseWords("Let's take LeetCode contest"))
// faster than 18.52% of JavaScript online submissions

2. 把 Stack 拿掉，效能更差 XD，我猜是因為每次都 unshift 很不好

var reverseWords = function(s) {
    let tmp = [];
    let result = [];
    for(let i = 0; i < s.length; i++){
        if(s.charAt(i) !== ' '){
            tmp.unshift(s.charAt(i))
        }else{
            result.push(tmp);
            result.push(' ');
            tmp = [];
        }
        
    }

    result.push(tmp);

    return result.reduce((acc, cur) => {
        return acc.concat(cur);
    }, []).join('');
};
console.log(reverseWords("Let's take LeetCode contest"))
// faster than 5.52% of JavaScript online submissions

改善

用 Two pointer 效能好多了。概念大概就是 result 直接去 += cStr[cStr.length-1-pointer]，Array get 超快

var reverseWords = function(s) {
    let sArray = s.split(" "), result="";
    for(var i=0;i < sArray.length;i++){
        let cStr = sArray[i];  // Let's
        let pointer = 0;
        while(pointer < cStr.length){
            result += cStr[cStr.length-1-pointer]; // 直接抓是 O(1)
            pointer++;
        }
        
        if( i < (sArray.length-1) ){
            result += ' ';
        }
    }
    return result;

};
console.log(reverseWords("Let's take LeetCode contest"))
// faster than 99.92% of JavaScript online submissions