Algorithm


Problem Name: 6. 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 s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

Input: s = "A", numRows = 1
Output: "A"

Constraints:

  • 1 <= s.length <= 1000
  • s consists of English letters (lower-case and upper-case), ',' and '.'.
  • 1 <= numRows <= 1000

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


char* convert(char* s, int numRows) {
    int len;
    int i, j, k = 0;
    char *p;
    int step, up;
    
    if (!s || !*s || numRows == 1) return s;
    
    len = strlen(s);
    p = malloc((len + 1) * sizeof(char));
    //assert(p);
    
    step = (numRows - 1) * 2;       // max span
    
    for (i = 0; i  <  numRows; i ++) {
        j = i;                      // first letter of each row
        up = 1;
        while (j  <  len) {
            p[k ++] = s[j];
            if (i == 0 || i == numRows - 1) {
                j += step;          // full span
            } else if (up) {
                j += step - i * 2;  // full span - offset
                up = 0;
            } else {
                j += i * 2;         // offset
                up = 1;
            }
        }
    }
    p[k] = 0;
    return p;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
s = "PAYPALISHIRING", numRows = 4

Output

x
+
cmd
"PINALSIGYAHRPI"

#2 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) return s;
        vector < string>v(numRows, "");
        int d = 1;
        int row = 0;
        for(auto c: s){
            v[row].push_back(c);
            row += d;
            if(row == numRows - 1) d = -1;
            if(row == 0) d = 1;
        }
        string res;
        for(auto x: v) res.append(x);
        return res;
    }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
s = "PAYPALISHIRING", numRows = 3

Output

x
+
cmd
"PAHNAPLSIIGYIR"

#3 Code Example with Java Programming

Code - Java Programming


class Solution {
  public String convert(String s, int numRows) {
    if (numRows == 1) {
      return s;
    }
    List < StringBuilder> list = new ArrayList<>();
    for (int i = 0; i  <  numRows; i++) {
      list.add(new StringBuilder());
    }
    int idx = 0;
    boolean downDirection = false;
    for (char c : s.toCharArray()) {
      list.get(idx).append(c);
      if (idx == 0 || idx == numRows - 1) {
        downDirection = !downDirection;
      }
      idx += downDirection ? 1 : -1;
    }
    StringBuilder result = new StringBuilder();
    for (StringBuilder sb : list) {
      result.append(sb.toString());
    }
    return result.toString();
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
s = "A", numRows = 1

Output

x
+
cmd
"A"

#4 Code Example with Javascript Programming

Code - Javascript Programming


const convert = function(s, numRows) {
  if (numRows === 1) {
    return s;
  }
  let output = "";
  for (let i = 1; i  < = numRows; i++) {
    let j = i - 1;
    let maxIncrement = 2 * numRows - 2;
    let increment = 2 * numRows - 2 - 2 * j;
    if (increment === 0) {
      increment = maxIncrement;
    } else {
      increment = maxIncrement - increment;
    }
    for (j; j  <  s.length; j += increment) {
      output += s[j];
      if (maxIncrement !== increment) {
        increment = maxIncrement - increment;
      }
    }
  }
  return output;
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
s = "PAYPALISHIRING", numRows = 3

Output

x
+
cmd
"PAHNAPLSIIGYIR"

#5 Code Example with Python Programming

Code - Python Programming


class Solution:
    def convert(self, s, numRows):
        if numRows == 1 or numRows >= len(s): return s
        row, direction, res = 0, -1, [""] * numRows
        for char in s:
            res[row] += char
            if row == 0 or row == numRows - 1: direction *= -1 
            row += direction
        return "".join(res) 
Copy The Code & Try With Live Editor

Input

x
+
cmd
s = "PAYPALISHIRING", numRows = 4

Output

x
+
cmd
"PINALSIGYAHRPI"

#6 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _006_ZigZagConversion
    {
        public string Convert(string s, int numRows)
        {
            if (numRows <= 1 || s.Length <= 1) { return s; }

            var result = new char[s.Length];
            var index = 0;
            for (int i = 0; i  <  numRows; i++)
            {
                for (int j = 0; (numRows * 2 - 2) * j + i  <  s.Length; j++)
                {
                    var originalIndex = (numRows * 2 - 2) * j + i;
                    result[index++] = s[originalIndex];

                    if (i == 0 || i == numRows - 1) { continue; }

                    originalIndex = originalIndex + (numRows * 2 - 2) - i * 2;
                    if (originalIndex  <  s.Length)
                    {
                        result[index++] = s[originalIndex];
                    }
                }
            }

            return new string(result);
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
s = "A", numRows = 1

Output

x
+
cmd
"A"
Advertisements

Demonstration


Previous
#05 Leetcode Longest Substring Without Repeating Characters Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#07 Leetcode - Reverse Integer Solution in Javascript, C, C++, C#, Java and Python leetcode