Leetcode – 6 – ZigZag Conversion

ZigZag Conversion

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)

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

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Description:

In this problem we have to show the string in a zig zag fashion ie. we have to split the string into number of rows. The number of columns can be adjusted so that the string fits in the number of rows specified.

Efficient solution: (Using String Builder array to store the rows)

If we think store each of the row in a string builder and have a running pointer that runs from 0 to 3

  • if it reaches 3 then decrement if it reaches 0 then increment
  • Keep adding the characters to the string builder
  • finally iterate j till the number of rows and append all the string builder array elements

1

Code:

public class Solution {
    public String convert(String s, int numRows) {
        if(s != null && !s.equals("")){

          int n = s.length();
          if(n == 1 || n < numRows)
            return s;
            
          int i=0;
          int j=0;
          StringBuilder[] sb = new StringBuilder[numRows];
          boolean endFlag = false;
          
          while(i<n){
            if(sb[j] == null){
                sb[j] = new StringBuilder();
            }

            sb[j].append(""+s.charAt(i++));
            if(!endFlag){
                j++;
                endFlag=false;
                if(j == numRows){
                    endFlag = true;
                    j--;
                }
            }
            
            if(endFlag){
                j--;
                endFlag=true;
                if(j == 0){
                    endFlag = false;
                }
            }
            
            if(j<0){
                j=0;
            }
            
          }

          j=0;
          StringBuilder result = new StringBuilder();
          while(j<numRows){
            result.append(sb[j++].toString());
          }
          
          return result.toString();
        }

        return "";
    }
}

Time Complexity: O(n)

  • Loop through the elements upto n – O(n)

Space Complexity: O(n)

  • We will be adding all the elements to the string builder which will be O(n)

Available Test Cases: 16

  • Check for null string as input
  • Check for duplicate elements
  • Check for spaces in  a string
  • Check for length less than number of rows given
  • Check for overflows
  • Check for rows over the length of the string

 Github:

Leetcode_6_ZigZag_Conversion

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: