---
# System prepended metadata

title: LeetCode 6. ZigZag Conversion (Java)
tags: [Java, leetcode, hashmap]

---

# LeetCode 6. ZigZag Conversion (Java)
###### tags: `leetcode` `Java` `hashmap`

## Description
> The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
> ```
> P   A   H   N
>A P L S I I G
>Y   I   R
> ```
>And then read line by line: "PAHNAPLSIIGYIR"
>Write the code that will take a string and make this conversion given a number of rows:
>```
>string convert(string s, int numRows);
>```

>拉囉

## Example
```
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR" 
```
```
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I
```
```
Input: s = "A", numRows = 1
Output: "A"
```

## Idea
:::warning
:warning: 因為剛學到Map，所以想學一下應用在題，但因此造成脫褲子放屁，這題我的演算法用List會簡單得多，runtime也會比較短。
:::
- **StringBuilder**=>和StringBuffer用法相似。使用目的為string的改動，**適用串連多個字串或改變字串裡內容**，String字串物件一旦產生後，其內容就是固定不可變的（immutable），亦即<font color="red">字串內容無法做任何的更改</font>。
![string](https://i.imgur.com/IqSeQWu.png =350x)
- 只使用一個迴圈，並加上變數控制``cur_level``是目前第幾行，``down``等於true時表示到了最下面那行並對``cur_level``做反向加減
- 最後再將結果append到``result``裡並回傳
## Code
雖然時間複雜度為$O(n)$，但如果用List就不用在額外使用map中的key，否則就會多出額外的運行時間
```java=
class Solution {
    public String convert(String s, int numRows) {
        if(numRows == 1) return s;
        Map <Integer, StringBuilder> map = new HashMap<>();
        int cur_level = 0;//目前第幾層
        boolean down = false; //最底層，要反轉加減
        for (int i = 0;i < s.length();i++){
            if(i < numRows ){
                map.put(cur_level, new StringBuilder());//先建立numRows個層數到map的key
            }
            if(map.containsKey(cur_level))
                map.get(cur_level).append(s.charAt(i));
            
            if(down == true){//到最底層，反轉加減
                cur_level--;    
            }
            else cur_level++;
            
            if(cur_level + 1 == numRows){
                down = true;
            }
            else if(cur_level == 0) down = false;
        }
        
        StringBuilder result = new StringBuilder();
        for (int i = 0;i < map.size();i++){
            result.append(map.get(i));//將map裡的每個key的value逐一加進去result
        }
        return result.toString();//注意!!這邊要將StringBuilder轉成真正的String型態
    }
}
```
## Result
Runtime: **11** ms, faster than **37.57%** of Java online submissions for ZigZag Conversion.
Memory Usage: **39.8** MB, less than **39.96%** of Java online submissions for ZigZag Conversion.