String Zigzag Conversion

Question

Overview

The string 0123456789 is written in a zigzag pattern (following the path going all the way down, then diagonally moving towards the top right) using a given number of rows. Like this example in the case of 3 rows.

0 4 8
1 3 5 7 9
2 6

This string is then read line by line and converted into a new string. In this case this new string from the zigzag will be 0481357926.

I'd like to understand any optimizations I can make using C++17 features, edge cases I may gave missed, possible overflows errors, etc.

#include <cmath>
#include <iostream>
#include <string>
class Solution {
 public:
 std::string convert(const std::string& s, const int numRows) {
 if (numRows == 1) { return s; }
 const int size = s.size();
 std::string converted = "";
 const int num = numRows + (numRows - 2);
 int row = 0;
 int i = 0;
 int sub = 0;
 bool useDiff = true;
 while (row < numRows) {
 converted += s[row];
 if (row == 0 || row == numRows - 1) {
 i = row + num;
 while (i < size) {
 std::string str(1, s[i]);
 converted.append(str);
 i += num;
 }
 } else {
 int diff = std::abs(num - sub);
 i = diff;
 while (i < size && row + i < size) {
 if (useDiff) {
 std::string str(1, s[row + i]);
 converted.append(str);
 useDiff = false;
 i += sub;
 } else {
 std::string str(1, s[row + i]);
 converted.append(str);
 useDiff = true;
 i += diff;
 }
 }
 }
 useDiff = true;
 sub += 2;
 row++;
 }
 return converted;
 }
};
int main()
{
 Solution solution;
 std::string s = "0123456789";
 int numRows = 3;
 std::cout << s << '\n';
 s = solution.convert(s, numRows);
 std::cout << s << '\n';
}

Answer 1

I see a number of things that may help you improve your program.

Use functions where appropriate

This is perhaps somewhat unusual advice to give for a C++ review, but there's not really any point to having convert be part of an object. It could function much more logically as a free function.

Simplify your code

The code currently includes these lines:

i = row + num;
while (i < size) {
 std::string str(1, s[i]);
 converted.append(str);
 i += num;
}

First, there's no need to create str because we can append a single character just as easily using push_back. Second, this would be better expressed as a for loop:

for (int i = row + num; i < size; i += num) {
 converted.push_back(s[i]);
}

Note also that i is now local to the for loop, minimizing the scope of the variable.

Take advantage of early returns

What you've got is a good start, but could be further adapted. First, if numRows == 1 or numRows >= s.size() then we can just return s. Second, if numRows is 0 or less, the current routine returns an empty string. Assuming that's correct behavior, we can put all of that into an early bailout at the head of the function:

const int size = s.size();
std::string converted = "";
if (numRows == 1 || numRows >= size) { 
 return s; 
} else if (numRows <= 0) {
 return converted;
}

Rethink the algorithm

The code already correctly calculates the variable num (which could use a better name, by the way -- maybe period). One way to think of this is that we process columns. Each column is period units wide. Within that column, either 1 or 2 numbers are printed. There is 1 number if it's the first or last row or 2 if it's any other. For example, if there are 4 rows, the array looks like this:

0 6
1 5 7
2 4 8
3 9

We can think of each column having two delta values that add up to a period. For each line, the deltas are as follows:

0 6 delta{6, 0}
1 5 7 delta{4, 2}
2 4 8 delta{2, 4}
3 9 delta{0, 6}

It's clear that the delta values must always add up to the period and that their usage alternates for each line. Also, if we're going to increment, it doesn't make much sense to increment by 0, so everywhere 0 appears as a delta value, we can replace with the period. I wrote a little class to handle that and the increments automatically:

class SaturatingInt {
public: 
 SaturatingInt(int cap, int val=0) : cap{cap}, val{val % cap} {}
 SaturatingInt &operator+=(int num) { val = (num + val) % cap; return *this; }
 SaturatingInt &operator-=(int num) { val = (cap + val - num) % cap; return *this; }
 int value() const { return val ? val : cap; }
private:
 int cap;
 int val;
};

Now here's the convert function using that class:

std::string convert(const std::string& s, const int numRows) {
 const int size = s.size();
 std::string converted = "";
 if (numRows == 1 || numRows >= size) { 
 return s; 
 } else if (numRows <= 0) {
 return converted;
 }
 const int period = numRows + (numRows - 2);
 std::array<SaturatingInt, 2> delta{period, period};
 for (int row = 0; row < numRows; ++row) {
 bool delta_index{true};
 for (int i{row}; i < size; i += delta[delta_index].value()) {
 converted.push_back(s[i]);
 delta_index = !delta_index;
 }
 delta[0] -= 2;
 delta[1] += 2;
 }
 return converted;
}

I tested that using this main:

int main()
{
 std::string s = "0123456789";
 for (int i = 0 ; i < 12; ++i) {
 std::cout << i << '\t' << convert(s, i) << '\n';
 }
}

And here are the results:

0 
1 0123456789
2 0246813579
3 0481357926
4 0615724839
5 0817926354
6 0192837465
7 0123948576
8 0123459687
9 0123456798
10 0123456789
11 0123456789

Answer 2

1. Don't use an alibi-class. It doesn't make the code any more OO, even in the cases it would be desirable, it just adds to the clutter.

2. Solution and convert are such generic names. Naming is hard, but good names really help.

3. You know an int need not be positive? An unsigned type may be more appropriate for a count, but even then you should handle zero.

4. Only if you need a null-terminated string should you consider a parameter of type std::string const&. In all other cases, using std::string_view is more efficient.

5. While creating a temporary string of length 1 probably doesn't cause dynamic allocation due to small-string-optimisation (or allocation ellision), doing so just to add a character to the result-string is cumbersome and potentially quite inefficient (in theory, the compiler could optimise it all out). Just append it directly.

6. If you assign directly, diff is gone.

7. useDiff doesn't make a difference, so remove it.

8. Consider adding additional test-cases. For that, you should rewrite main().

See the modified code live on coliru:

#include <string>
#include <string_view>
#include <stdexcept>
auto zigzag(std::string_view s, std::size_t cRows) {
 if (!cRows)
 throw std::domain_error("Must output at least one row.");
 if (!cRows || cRows >= s.size())
 return std::string(s);
 std::string r;
 r.reserve(s.size());
 const auto period = 2 * cRows - 2;
 for (auto row = 0 * cRows; row < cRows; ++row) {
 auto delta = 2 * row;
 auto delta2 = period - delta;
 if (!delta) delta = period;
 if (!delta2) delta2 = period;
 for (auto i = row; i < s.size(); i += delta) {
 r += s[i];
 std::swap(delta, delta2);
 }
 }
 return r;
}
#include <iostream>
struct test {
 std::string_view in;
 std::size_t n;
 std::string_view out;
};
int main() {
 constexpr test cases[]{
 "0123456789", 3, "0481357926",
 "", 1, "",
 "0123456789", 10, "0123456789",
 "0123456789", 2, "0246813579",
 };
 for (auto&& x : cases) {
 std::cout << "zigzag(\"" << x.in << "\", " << x.n << ") == \"" << x.out;
 auto r = zigzag(x.in, x.n);
 if (r == x.out)
 std::cout << "\": PASSED\n";
 else
 std::cout << "\": FAILED, got \"" << r << "\"\n";
 }
}

• Toby Speight: I've not heard the term "alibi class" for this before? Is it a widely-used term? A simple web search didn't find a definition.
• Deduplicator: @TobySpeight No, it isn't widely used. But as it is a bad alibi when accused of being insufficiently OOP-minded, and has no other use, I thought it fit.
• Toby Speight: It's a good phrase; I think we should popularise it some more!

Answer 3

So from a generic perspective I would suggest to cut the task into different sub tasks

Determine, which row the character is in. You can determine this generically from the position the character has in the string.

Note that this is completely determined by the size of the zigzag pattern and effectively independentof the string itself.

Then sort the string by that index. If your algorithm creates an [x,y] Coordinate you simply need so sort via

constexpr friend bool operator<(const Coordinate& a, const Coordinate& b) {
 return std::tie(a.y, a.x) < std::tie(b.y,b.x);
}

So one simple way would be to create an array of indexes and sort that as coordinate and then create the string from the the index array

• Toby Speight: You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer.