Placement

Leet code :Zigzag Conversion solution c++ , Java , Python , JavaScript , Swift ,TypeScript

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"

Approach 1: Sort by Row

Intuition

By iterating through the string from left to right, we can easily determine which row in the Zig-Zag pattern that a character belongs to.

:

Approach 2: Visit by Row

Intuition

Visit the characters in the same order as reading the Zig-Zag pattern line by line.

C++ solution :

class Solution {
public:
    string convert(string s, int numRows) {
        int n = numRows;
        string str;
        if(n == 0 || n == 1){ return s; }
            
        for(int i = 0; i < s.length(); i += (n-1)*2){
            str += s[i];
        }
        
        for(int j = 1; j < n-1; j++)
        {
            bool goDown = true;
             for(int i = j; i < s.length();){
                 str += s[i];
                 if(goDown){
                      i+=(n-j-1)*2;
                 }else{
                     i+=(n-1)*2-(n-j-1)*2;
                 }
                 goDown = !goDown;
             }
            
        }
        
        for(int i = n-1; i < s.length(); i += (n-1)*2){
            str += s[i];
        }
        return str;
    }
};

Python Solution :

 def convert(self, s, numRows):
        if numRows == 1:
            return s
        string = ""
        step = (numRows - 1)*2
        down = 0 
        for i in range(numRows):
            if i < len(s):
                string += s[i]
            j = i
            while j < len(s):
                j += step
                if(step and j < len(s)): 
                    string += s[j]
                j += down
                if(down and j <len(s)):
                    string += s[j]
            step -= 2
            down += 2
        return string

Java Solution

class Solution {
public String convert(String s, int numRows) {
    if (numRows == 1) return s;

    List<StringBuilder> rows = new ArrayList<>();
    for (int i = 0; i < Math.min(numRows, s.length()); i++)
        rows.add(new StringBuilder());

    int curRow = 0;
    boolean goingDown = false;

    for (char c : s.toCharArray()) {
        rows.get(curRow).append(c);
        if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
        curRow += goingDown ? 1 : -1;
    }

    StringBuilder ret = new StringBuilder();
    for (StringBuilder row : rows) ret.append(row);
    return ret.toString();}

}

Java Approach 2 :

class Solution {
    public String convert(String s, int numRows) {

        if (numRows == 1) return s;

        StringBuilder ret = new StringBuilder();
        int n = s.length();
        int cycleLen = 2 * numRows - 2;

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < n; j += cycleLen) {
                ret.append(s.charAt(j + i));
                if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                    ret.append(s.charAt(j + cycleLen - i));
            }
        }
        return ret.toString();
    }
}

Facebook
Twitter
LinkedIn

Leave a Comment