The String ZigZag Conversion Algorithms

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

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

推荐阅读：
山东启动打击非法保健食品专项行动　 盘点那些不科学不健康的饮食习惯　 养生推荐：几种最牛的常见抗衰老食物　 营养健康食品系列：休闲干果开心果　 营养健康食品：向日葵的种子葵花籽　 酿造酒之黄酒和白酒的营养价值　 葡萄酒及啤酒的营养保健价值　 保健食品广告九成以上虚假违法　 生吃鸡蛋易引起沙门氏菌食物中毒　 由副溶血弧菌污染引起的食物中毒　
评论列表
添加评论