# 6.ZigZag Conversion

## 1.問題

* 將鋸齒狀排列的字串還原

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LIF1R2AIAsSOzkYqZMI%2F-LIKOniHkm2Wo081V3iF%2F2018072601.jpg?alt=media\&token=c518d4b3-fc7e-474a-ace9-a05869d7e682)

## 2.想法 

* 將鋸齒狀的序列依正反不同的方向放入numRows個vector中
  * 當碰到頂點時, 反轉放入vector的順序
* 將vectors所儲存的字元都放入回傳的字串中
* 當numRows為1時, 直接回傳s

## 3.程式碼

```
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows <= 1) {
            return s;  
        } 
        vector<string> res(numRows, "");
        int step = 1, row = 0;
        for (int i = 0 ; i < s.size(); i++) {
            res[row] += s[i];
            if (row == 0) {
                step = 1;
            }
            if (row == numRows - 1) {
                step = -1;
            }
            row += step;
        }
        string str;
        for (int i = 0 ; i < numRows; i++) {
            for (int j = 0 ; j < res[i].size(); j++) {
                str += res[i][j];
            }
        }
        return str;
    }
};
```

## 4.Performance

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LIF1R2AIAsSOzkYqZMI%2F-LIKP6je56b8ZmvlbsQ0%2F2018072602.jpg?alt=media\&token=4e015fe2-aa12-47d0-a9fe-0170c7411b2c)