The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows…
- User
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 Example 3:
Input: s = "A", numRows = 1 Output: "A"
Constraints:
1 <= s.length <= 1000 s consists of English letters (lower-case and upper-case), ',' and '.'. 1 <= numRows <= 1000
- Assistant
To solve the ZigZag Conversion problem, you can simulate the process of writing the characters of the input string
sin a zigzag pattern across the specified number of rows (numRows). Here's a step-by-step explanation followed by the implementation in C++.Approach:
-
Edge Case Handling:
- If
numRowsis 1 or greater than or equal to the length of the strings, the zigzag conversion is unnecessary. In such cases, return the original strings.
- If
-
Initialize Data Structures:
- Create a vector of strings, where each string represents a row in the zigzag pattern.
-
Simulate ZigZag Writing:
- Use a variable
currentRowto keep track of the current row where the next character should be placed. - Use a boolean
goingDownto determine the direction of traversal (downwards or upwards in the zigzag). - Iterate through each character in the string
sand append it to the appropriate row in therowsvector. - Change the direction (
goingDown) when you reach the top (currentRow == 0) or the bottom (currentRow == numRows - 1) row.
- Use a variable
-
Concatenate Rows:
- After placing all characters in their respective rows, concatenate all the strings in the
rowsvector to form the final converted string.
- After placing all characters in their respective rows, concatenate all the strings in the
C++ Implementation:
#include <iostream> #include <vector> #include <string> using namespace std; class Solution { public: string convert(string s, int numRows) { // Edge case: if numRows is 1 or greater than the string length if (numRows == 1 || numRows >= s.length()) { return s; } // Initialize a vector of strings for each row vector<string> rows(min(numRows, (int)s.length())); int currentRow = 0; bool goingDown = false; // Iterate through each character in the string for (char c : s) { rows[currentRow] += c; // Change direction if we are at the first or last row if (currentRow == 0 || currentRow == numRows - 1) { goingDown = !goingDown; } // Move up or down currentRow += goingDown ? 1 : -1; } // Concatenate all rows to get the final string string converted; for (string row : rows) { converted += row; } return converted; } }; // Helper function to run test cases void runTestCase(string s, int numRows, string expected) { Solution solution; string result = solution.convert(s, numRows); cout << "Input: s = \"" << s << "\", numRows = " << numRows << "\n"; cout << "Output: \"" << result << "\"\n"; cout << "Expected: \"" << expected << "\"\n"; cout << (result == expected ? "✅ Passed" : "❌ Failed") << "\n\n"; } int main() { // Example Test Cases runTestCase("PAYPALISHIRING", 3, "PAHNAPLSIIGYIR"); runTestCase("PAYPALISHIRING", 4, "PINALSIGYAHRPI"); runTestCase("A", 1, "A"); runTestCase("AB", 1, "AB"); runTestCase("ABCDEFG", 2, "ACEGBDF"); return 0; }Explanation of the Code:
-
Edge Case Check:
- If
numRowsis 1 or the number of rows is greater than or equal to the length of the string, return the original string since no zigzag conversion is needed.
- If
-
Initialization:
vector<string> rows(min(numRows, (int)s.length())): Initializes a vector with a size equal to the smaller ofnumRowsor the string's length to handle cases where the string is shorter than the number of rows.currentRow: Tracks the current row index where the character should be placed.goingDown: A boolean flag indicating the direction of traversal.
-
Iterating Through the String:
- For each character
cin the strings:- Append
cto thecurrentRowinrows. - If the
currentRowis at the top or bottom, toggle thegoingDownflag to change direction. - Update
currentRowby incrementing or decrementing based on thegoingDownflag.
- Append
- For each character
-
Concatenating Rows:
- After all characters are placed in their respective rows, iterate through the
rowsvector and concatenate all the strings to form the final converted string.
- After all characters are placed in their respective rows, iterate through the
-
Testing:
- The
runTestCasefunction is a helper to run and verify test cases against expected outcomes. - The
mainfunction includes multiple test cases, including the examples provided, to demonstrate the correctness of the implementation.
- The
Output:
When you run the above code, it will produce the following output:
Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR" Expected: "PAHNAPLSIIGYIR" ✅ Passed Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Expected: "PINALSIGYAHRPI" ✅ Passed Input: s = "A", numRows = 1 Output: "A" Expected: "A" ✅ Passed Input: s = "AB", numRows = 1 Output: "AB" Expected: "AB" ✅ Passed Input: s = "ABCDEFG", numRows = 2 Output: "ACEGBDF" Expected: "ACEGBDF" ✅ PassedEach test case confirms that the implementation correctly performs the zigzag conversion as per the provided examples and additional cases.
Complexity Analysis:
- Time Complexity: O(n), where n is the length of the string
s. We iterate through each character once. - Space Complexity: O(n), since we store all characters in the
rowsvector.
This solution is efficient and handles all edge cases within the specified constraints.
-