6. ZigZag Conversion

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)

And then read line by line: "PAHNAPLSIIGYIR"

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: s = "PAYPALISHIRING", numRows = 3

Output: "PAHNAPLSIIGYIR"

Explanation:

Example 2

Input: s = "PAYPALISHIRING", numRows = 4

Output: "PINALSIGYAHRPI"

Explanation:

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public String convert(String s, int numRows) {
        if(s.length() == 1 || numRows <= 1) return s;
        int row = 0;
        int n = s.length();
        boolean down = true;
        
        String[] arr = new String[n];
        Arrays.fill(arr, "");
        
        for(int i = 0; i < n; i++) {
            arr[row] += s.charAt(i);
            
            if(row == numRows-1) {
                down = false;
            } else if(row == 0) {
                down = true;
            }
            if(down) {
                row++;
            } else {
                row--;
            }
        }
        return String.join("", arr);
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public String convert(String s, int numRows) {
        if(s.length() == 1 || numRows <= 1) return s;
        int row = 0;
        int n = s.length();
        boolean down = false;
        
        String[] arr = new String[numRows];
        Arrays.fill(arr, "");
        
        for(char ch: s.toCharArray()) {
            arr[row] += ch;
            if(row == numRows-1 || row == 0) down = !down;
            row += (down ? 1: -1);
        }
        
        return String.join("", arr);
    }
}

Solution 3

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public String convert(String s, int numRows) {
        int n = s.length();
        if(n == 1 || numRows <= 1 || numRows > n) return s;
        int interval = (2 * numRows) - 2;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < numRows; i++) {
          int step = interval - (2 * i);
          for(int j = i; j < n; j += interval) {
              sb.append(s.charAt(j));
              if(step > 0 && step < interval && (j+step) < n) {
                  sb.append(s.charAt(j+step));
              }
          }
        }
        return sb.toString();
    }
}

Follow up