O(n) solution with simple direction switching


  • 0
    J
    public class Solution {
        public static String convert(String s, int numRows) {
            
            if (s == null || s.length() == 0)
                return "";
            
            if (numRows == 1)
                return s;
            
            StringBuffer[] strings = new StringBuffer[numRows];
            
            for (int i = 0; i < numRows; i++) {
                strings[i] = new StringBuffer();
            }
            
            // Idea here is to change the direction when we reach at the end of the rows and count backwards 
            // until we reach 0 and change dir again....
            int j = -1;
            int down = 0;
            int up = 1;
            int dir = down;
            for (int i = 0; i < s.length(); i++) {
                if (dir == down) {
                    j++;
                    strings[j] = strings[j].append(s.charAt(i));      
                    if (j == numRows - 1) {
                       dir = up;
                    }
                }
                else {
                    j--;
                    strings[j] = strings[j].append(s.charAt(i));
                    if (j == 0)
                        dir = down;
                }      
            }
            
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < numRows; i++) {
                sb.append(strings[i]);
            }
            return sb.toString();
        }
    }

  • 1

    Bit shorter main part...

    int j = 1, dir = -1;
    for (int i = 0; i < s.length(); i++) {
        j += dir;
        strings[j].append(s.charAt(i));
        if (j == 0 || j == numRows - 1)
            dir = -dir;
    }
    

Log in to reply
 

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