Question
Formatted question description: https://leetcode.ca/all/6.html
6. ZigZag Conversion
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
Algorithm
Law: The first and last lines are added in the order of 2n-2. The position of the word diagonally across the line is the current column j+(2n-2)-2i
(i is the index of the row).
Code
Java
-
public class ZigZag_Conversion { public class Solution { public String convert(String s, int nRows) { if (s == null || s.length() <= nRows || nRows == 1) { return s; } StringBuilder sb = new StringBuilder(); for (int i = 0; i < nRows; i++) { if (i == 0 || i == nRows - 1) { int index = i; while (index < s.length()) { sb.append(s.charAt(index)); index += 2 * (nRows - 1); } } else { int index = i; while (index < s.length()) { sb.append(s.charAt(index)); if (index + 2 * nRows - 2 * i - 2 < s.length()) { sb.append(s.charAt(index + 2 * nRows - 2 * i - 2)); } index += 2 * (nRows - 1); } } } return sb.toString(); } } }
-
// OJ: https://leetcode.com/problems/zigzag-conversion/ // Time: O(N) // Space: O(1) class Solution { public: string convert(string s, int numRows) { if (numRows == 1) return s; int N = s.size(), d = (numRows - 1) * 2; string ans; for (int i = 0; i < numRows; ++i) { int w = 2 * i; for (int j = i; j < N;) { ans += s[j]; w = d - w; if (!w) w = d; j += w; } } return ans; } };
-
class Solution(object): def convert(self, s, numRows): """ :type s: str :type numRows: int :rtype: str """ if numRows <= 1: return s n = len(s) ans = [] step = 2 * numRows - 2 for i in range(numRows): one = i two = -i while one < n or two < n: if 0 <= two < n and one != two and i != numRows - 1: ans.append(s[two]) if one < n: ans.append(s[one]) one += step two += step return "".join(ans)