The String ZigZag Conversion Algorithms
- 时间:2020-09-12 10:17:13
- 分类:网络文摘
- 阅读:93 次
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 RAnd 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) —
推荐阅读:New App Protects You From Becoming A Victim Of White Collar Crim Sprout Social Develops Bot Builder for Automated Conversational Which Analytics Stats Really Matter to Your Blog and Marketing C 7 Tools to Help You find Out How Fast Your Blog Loads The Superheroes of Video Marketing Infographic 10 Reasons Why You’re Not Getting Social Shares On Your Blog 5 Companies That Are Winning with Social Data and Email Marketin How to Assure Your Customers That It’s Safe to Shop With You 5 Corporate Blogs that Bloggers Can Learn From 5 Rules to Create Successful Crypto-Related Content
- 评论列表
-
- 添加评论