leetcode 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 text, int nRows); convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

解决方案： The idea is, the first row and last row has no offset. Each element has a fixed difference of 2(nRows-1); For the rows in between, there is a incremental offset of 2;

0 6 12 -> distance = 2(nRows-1) = 6 offset = 0 1 5 7 11 -> offset = distance - 2 = 4 2 4 8 10 -> offset = distance -2 -2 = 2 3 9 -> distance = 2(nRows-1) = 6 offset = 0

Easy to observe. There is a catch, that you need to add the offset element with previous regular element. 5 follows 1, 4 follows 2. Otherwise, you will miss the tail if there is no vertical column in the end.Looks like a CS homework:)

class Solution {
public:
    string convert(string s, int nRows) {
        if(s.length() == 0 || 
            s.length()/nRows < 1 ||
            nRows == 1) 
        {
            return s;
        }
        int distance = 2*(nRows-1);
        string result;
        int offset = 0;
        for (int row = 0; row < nRows; row++)
        {
            for (int index = row; index < s.length(); index += distance)
            {
                result+=s[index];
                if (offset != 0 && index + distance - offset < s.length())
                {
                    result+=s[index + distance - offset];
                }
            }
            offset += 2;
            offset = offset % distance;
        }
        return result;
    }
};

解决方案2：

这里写图片描述

The problem statement itself is unclear for many. Especially for 2-row case. “ABCD”, 2 –> “ACBD”. The confusion most likely is from the character placement. I would like to extend it a little bit to make ZigZag easy understood.

The example can be written as follow: 1.P…….A……..H…….N 2…A..P….L..S….I…I….G 3…..Y………I……..R

Therefore,

class Solution {
public:
    string convert(string s, int numRows)
    {


    if (numRows <= 1)
        return s;

    const int len = (int)s.length();
    string *str = new string[numRows];

    int row = 0, step = 1;
    for (int i = 0; i < len; ++i)
    {
        str[row].push_back(s[i]);

        if (row == 0)
            step = 1;
        else if (row == numRows - 1)
            step = -1;

        row += step;
    }

    s.clear();
    for (int j = 0; j < numRows; ++j)
    {
        s.append(str[j]);
    }

    delete[] str;
    return s;
}
};

python解决方案： The idea is to use the remainder (index%period) to determine which line the character at the given index will be. The period is calculated first based on nRows. A dictionary with remainder:line as key:value is then created (this can also be done with a list or a tuple). Once these are done, we simply go through s, assign each character to its new line, and then combine these lines to get the converted string.

The code may be further shortened by using dict comprehension:

d={i:i if i

def convert(self, s, nRows):
    if nRows==1:
        return s
    period= 2*(nRows -1)
    lines=["" for i in range(nRows)]
    d={} # dict remainder:line
    for i in xrange(period):
        if i<nRows:
            d[i]=i
        else:
            d[i]=period-i

    for i in xrange(len(s)):
        lines[ d[i%period] ] +=s[i]

    return "".join(lines)