Easiest O(n) Java solution with only ONE StringBuilder!!!


  • 0
    J

    If numRows is less than 2, then we can just return the original string. Likewise, if numRows is greater than or equal to the length of the original string, we can just return the original string. I explain how to handle the more interesting, general cases below.

    Consider the following example: convert("PAYPALISHIRING", 5).

    This is the desired result:
    alt text
    => "PHASIYIRPLIGAN"

    Notice that each instance of the zigzag pattern is of length numRows + (numRows - 2). Notice that this value is even. In our example, the first instance of the zigzag pattern is "PAYPA" + "LIS".

    1. For each instance of the zigzag pattern, we first iterate over the first (i.e. 0th) character. In our example, for the first instance, we pick the first 'P'.
    2. Then, for each instance of the zigzag pattern, for j = 1 ... (length of pattern / 2) - 1, we iterate over the jth as well as the (length of pattern - j)th characters. In our example, for the first instance, for j = 1, we pick 'A' and 'S'. For j = 2, we pick 'Y' and 'I'. And so on.
    3. Finally, for each instance of the zigzag pattern, we iterate over the (length of pattern / 2)th character. In our example, for the first instance, we pick the second 'A'.

    By iterating over the characters of the input string in this order, we are guaranteed to step through each character once, giving us an O(n) algorithm using only one StringBuilder. The code below reflects this algorithm.

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

    Please let me know if anything is unclear! :)


Log in to reply
 

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