The String ZigZag Conversion Algorithms

  • Time：2020-09-12 10:17:13
  • Class：Weblog
  • Read：24

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

The String ZigZag Conversion Algorithms

We can simulate the process by walking down first, then when it reaches the last row, bounces back in the reverse direction. We need arrays of strings as we walk, and append the characters to the corresponding row of string.

O(N) time and O(N) space requirement. Edge case is when the ZigZag row is one and then we have to return the original string.

C++ String ZigZag Conversion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        vector<string> rows(min((int)s.size(), numRows));
        bool down = false;        
        int row = 0;
        for (int i = 0; i < s.size(); ++ i) {
            rows[row] += s[i];
            if ((row == 0) || (row == numRows - 1)) {
                down = !down;
            }
            row += down ? 1 : -1;
        }        
        string ss = "";
        for (const auto &n: rows) {
            ss += n;
        }
        return ss;
    }
};
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        vector<string> rows(min((int)s.size(), numRows));
        bool down = false;        
        int row = 0;
        for (int i = 0; i < s.size(); ++ i) {
            rows[row] += s[i];
            if ((row == 0) || (row == numRows - 1)) {
                down = !down;
            }
            row += down ? 1 : -1;
        }        
        string ss = "";
        for (const auto &n: rows) {
            ss += n;
        }
        return ss;
    }
};
Python String ZigZag Conversion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        data = [''] * numRows
        down = False
        row = 0
        for i in s:
            data[row] += i
            if row == 0 or row == numRows - 1:
                down = not down
            row = row + 1 if down else row - 1
        x = ''
        for j in data:
            if j != '':
                x = x + j
        return x
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        data = [''] * numRows
        down = False
        row = 0
        for i in s:
            data[row] += i
            if row == 0 or row == numRows - 1:
                down = not down
            row = row + 1 if down else row - 1
        x = ''
        for j in data:
            if j != '':
                x = x + j
        return x
Javascript String ZigZag Conversion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    if (numRows === 1) return s;
    let data = [];
    let row = 0;
    let down = false;
    for (let x of s) {
        if (typeof data[row] === 'undefined') {
            data[row] = x;
        } else {
            data[row] += x;
        }
        if (row === 0 || row === numRows - 1) {
            down = !down;
        }
        row += down ? 1 : -1;
    }
    let res = '';
    for (let i = 0; i < Math.min(numRows, s.length); ++ i) {
        res += data[i];
    }
    return res;
};
/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    if (numRows === 1) return s;
    let data = [];
    let row = 0;
    let down = false;
    for (let x of s) {
        if (typeof data[row] === 'undefined') {
            data[row] = x;
        } else {
            data[row] += x;
        }
        if (row === 0 || row === numRows - 1) {
            down = !down;
        }
        row += down ? 1 : -1;
    }
    let res = '';
    for (let i = 0; i < Math.min(numRows, s.length); ++ i) {
        res += data[i];
    }
    return res;
};

–EOF (The Ultimate Computing & Technology Blog) —

Recommend：
Iterative and Recursion Algorithms to Compute the Number of Step
How to Check if a DLL or EXE is 32-bit or 64-bit (x86 or x64) us
C++: How to Iterate the Elements over the Sets (set, unordered_s
How to Iterate over the Items in Java’s Map (HashMap, Hash
Dynamic Programming Algorithm to Count Vowels Permutation
Exploring the Importance of Brand Consistency
Cleaning A WordPress Malware Infection For Dummies
7 Killer Ways to Higher Average Time on Page
6 Tips for Creating Infographics to Make Your Blog Stand Out
11 Foolproof Hacks to Drive Traffic to Your Blog in 2019
Share：Facebook Twitter
Comment list
Comment add