JAVA Zig Zag Conversion (Simple)

  • 2

    A simple solution to tackling the Zig Zag Conversion problem is using an array of strings. We first take care of trivial cases where the length of the String s is 0 or 1 or even when int numRows is 1.

    We know that each character of String s belongs in a specific row, and the for loop will take care of placing each character in the appropriate row. We start off by creating a boolean down variable which tells us whether we should continue going down to the next row or not and the int row value to indicate which row we are currently on. We traverse through the characters of String s, converting each character to a string so we can append it onto the appropriate row. Moreover, in the for loop, we constantly check if we are on the last or first row, and assign boolean down truth values accordingly. If we are going down, we increase the row value by 1, else we decrease by 1.

    In the last section of the code, we return the final String zig_zag, which appends all the rows present in String rows[], and we also take care of null characters.

    class Solution {
        public String convert(String s, int numRows) {
           String rows[] = new String[numRows];
           if (s.length() == 0 || s.length()==1 || numRows == 1) 
               return s;
           boolean down = true; 
           int row = 0; 
           for (int i = 0; i < s.length(); i++) {
               String ch = Character.toString(s.charAt(i));
               rows[row] += ch;
               if (row == numRows-1) 
                   down = false;
               else if (row == 0)
                   down = true;
               if (down) 
           String zig_zag = "";
           for (int i = 0; i < numRows; ++i) 
                zig_zag += rows[i];
           zig_zag = zig_zag.replaceAll("null", "");
           return zig_zag;

    Complexity Analysis:

    Time complexity : O(n). We traverse the characters of the string exactly once.

    Space complexity : O(2n). The extra space required for storing the characters in String array as well as returning them.

  • 0

    @veeeee17 Very good solution (because it's the same as mine :-P) except I recommend using StringBuffers instead of Strings or else your complexity isn't really O(n) because every String + String operation actually copies the entire buffer.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.