The String ZigZag Conversion Algorithms

  • 时间：2020-09-12 10:17:13
  • 分类：网络文摘
  • 阅读：136 次

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) —

推荐阅读：
饮食与健康：维生素B2的补充无需刻意　 女性急躁易发怒可能与维生素缺乏有关系　 冬天吃水果，究竟应该注意什么问题？　 萝卜的保健功能和萝卜的食疗吃法　 红枣美味营养可养生但是禁忌亦不少　 不同包装的牛奶，你知道该如何选择吗　 冬天吃羊肉如何去掉羊膻味及饮食禁忌　 适度喝啤酒预防骨质疏松保持关节弹性　 关于鸡蛋营养及其食用方法的十大误区　 腊肉的风味和特点及腊肉的制作全过程　
评论列表
添加评论