---
# System prepended metadata

title: 344. Reverse String
tags: [Leetcode]

---

# 344. Reverse String
## 題目敘述
![](https://i.imgur.com/RBFkrrV.jpg)

## 初步想法
我一剛開始是覺得可以直接用內建function reverse，但設想如果在其他語言中沒有這個結構該怎麼辦?於是乎有了其他辦法。


## 解題

### W1 直接用 reverse

```
var reverseString = function(s) {
    s.reverse(); 
};
```
#### 說明:
reverse() 方法用來將陣列倒轉，將第一個元素換到最後一個，最後一個元素換到第一個，依此類推，返回倒轉後的陣列。 因此不用在意[in place](https://en.wikipedia.org/wiki/In-place_algorithm)的問題

### W2 雙指針

```
var reverseString = function(s) {
    let left = 0
    let right = s.length-1
    while(left < right){
        [s[left], s[right]] = [s[right], s[left]]
        left ++
        right--
    }
};
```

#### 說明:
JavaScript ES6 寫法
```
let a = 1, b = 2;
[a, b] = [b, a]
```
#### 時間複雜度: O(logn)

#### 疑問:
其中我在while多加一道比較，在兩者內容不同的前提下在做交換，想減少其交換的次數，但error

```
var reverseString = function(s) {
    let left = 0
    let right = s.length-1
    while(left < right && s[left] != s[right]){
        [s[left], s[right]] = [s[right], s[left]]
        left ++
        right--
    }
};
```


### W3 half-loop

```
var reverseString = function(s) {
    for(let low = 0; low < s.length/2; low++){
        [s[low],s[s.length-low-1]] = [s[s.length-low-1],s[low]]
    }

};
```
#### 時間複雜度: O(n/2)


#### 補充:
請比較一下 一半的迴圈跟 **每次動**兩格(雙指針) 的時間複雜度?
每次動n格，有點像每次都少掉一半，
(1/2)*(1/2)*(1/2)*(1/2)*...(1/2)，乘n次，所以
是logn

### W4 遞迴
<!-- 這部分不太懂 之後需要再加強 -->

```
var reverseString = function(s) {
    var helper = function(left, right){
        if(left >= right)
            return
        [s[left], s[right]] = [s[right], s[left]]
        return helper(left + 1, right - 1)
    }
    return helper(0, s.length - 1)
};
```





#### 優點
1. 簡單好懂

#### 缺點
1. 一層層呼叫記憶體，造成記憶體占用

#### 補充:
必須知道如何將遞迴和迴圈做轉換




###### tags: `Leetcode`
