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

因為剛學到Map，所以想學一下應用在題，但因此造成脫褲子放屁，這題我的演算法用List會簡單得多，runtime也會比較短。

• StringBuilder=>和StringBuffer用法相似。使用目的為string的改動，適用串連多個字串或改變字串裡內容，String字串物件一旦產生後，其內容就是固定不可變的（immutable），亦即字串內容無法做任何的更改。
• 只使用一個迴圈，並加上變數控制cur_level是目前第幾行，down等於true時表示到了最下面那行並對cur_level做反向加減
• 最後再將結果append到result裡並回傳

Code

雖然時間複雜度為

$O(n)$，但如果用List就不用在額外使用map中的key，否則就會多出額外的運行時間

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.