Simple Solution for Zig Zag with Explanation


  • 0
    R

    This is a simple problem if you observe the pattern carefully.
    For example, consider the below test case.
    s="PAYPALISHIRINGHELLO"
    n=5

    The Pattern would be something like this:

    P    H       L
    A   S I     E L
    Y  I   R   H   O
    P L     I G
    A        N
    

    O/P: PHLASIELYIRHOPLIGAN

    Now if you observe, for every character i, the next character will be at index i+(n*2-2). Why n*2-2, its simple, n-1 steps to go down and n-1 steps to go up back to the same line.
    For example, while processing line 0, the next character after 'P' (index=0) will be 'H' (index=8), because it takes 4 steps to go down to the bottom most line and 4 steps to come back to the same line.
    So the next character will be at index 0+4+4 => 8 or 0+(5*2-2)=>8
    This n*2-2 will remain fixed for given n. So let's call it jumps i.e jumps=n*2-2
    Now, this holds only while processing the first and last line. For lines in between them, some additional task is to be done.
    For example, while processing Line 1, the first character is 'A' (index=1).
    The next character will be at index 1+jumps=>9. i.e 'I'
    But if you observe, 'S' comes between 'A' and 'I'. The key thing to note here is that second, fourth, sixth (all even) character at line j (where j>0 and j<n-1) will be at location i+jumps-(2*j). Again, the reason is simple, the previous character of i+jumps will at i+jumps-2*j for line j (0-based indexing), because the difference of indices between them is 2 for line1, 4 for line 2, 6 for line 3 and so on.
    Thus, the previous character for 'I' (index=9) will be at index 9-2=7 i.e 'S'

    Time Complexity is O(n) since we are visiting each character only once.
    Space Complexity is O(1).

    Read the code for better clarity of above exaplanation.

    string convert(string s, int numRows) {
            if(numRows==1)
                return s;
            int jumps=numRows*2-2;
            string ans="";
            for(int j=0;j<numRows;j++){
                int i=j;
                while(i<s.size()){
                    ans+=s[i];
                    i+=jumps;
                    if(j!=0 && j!=numRows-1 && i-2*j<s.size())
                        ans+=s[i-2*j];
                }
            }
            return ans;
        }
    

  • 0
    F

    Thanks! Here's the javafied version:

    class Solution {
        public String convert(String s, int numRows) {
            if (numRows==1) return s;
    
            int jumps = numRows*2 - 2; // Number of zigs
            StringBuilder ans = new StringBuilder();
            for (int j = 0; j < numRows; j++) {
                int i = j;
                while (i < s.length()) {
                    ans.append(s.charAt(i));
                    i += jumps;
                    if (j != 0 && j != numRows-1 && i - 2*j < s.length()) { // Check that not on first or last row
                        ans.append(s.charAt(i-2*j));
                    }
                }
            }
            return ans.toString();
        }
    }

  • 0
    V

    the running time of solution may be lower ?cause you used loops. Although the method is directly solve this problem. Is an optimized method existed?


Log in to reply
 

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