6. ZigZag Conversion (Medium)

https://leetcode.com/problems/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

Solutions

class Solution {

    // Zigzag is a pattern that repeats every numRows * 2 - 2 chars. To find out the
    // pattern, put the elements into a matrix.

    // The the row size is numRows, the columns size
    // should be (s.length() / (numRows * 2 - 2) + numRows - 1) * (numRows-1), where
    // s.length() / (numRows * 2 - 2) + 1 is the number of pattern groups.

    // Literally, adding 1 or not depends on specific situation. But to make it easier, I always advise
    // to add; numRows - 1 is the number of chars in each ziazag pattern.

    public String convert(String s, int numRows) {
        String ans = "";

        if (s == null || s.length() == 0) {
            return ans;
        }

        if (numRows == 1) {
            return s;
        }

        int len = s.length();

        int groupSize = 2 * numRows - 2;
        for (int i = 0; i < numRows; i++) {
            for (int j = i; j < len; j += groupSize) {
                ans += s.charAt(j);

                // Make sure char index is within the boundary.
                if (i % (numRows - 1) != 0 && j + groupSize - 2 * i < len) {
                    ans += s.charAt(j + groupSize - 2 * i);
                }
            }
        }

        return ans;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-02-25 12:54:04

results matching ""

    No results matching ""