Monday, May 18, 2015

ZigZag Conversion

Problem Statement

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".

Source: https://leetcode.com/problems/zigzag-conversion/
Programming Language: C#
Run Time Complexity: O(n)
Space Complexity: O(n)

Solution:

public string Convert(String s, int nRows)
{
    string result = "";

    // Input Validation
    if ((s == null) || (s.Length == 0))
        return result;

    // Input Validation
    if (nRows <= 0)
        return "";

    // Input Validation
    if (nRows == 1)
        return s;

    // Create Array of strings
    string[] strstr = new string[nRows];
            
    // Index for Array of strings 
    int strstrIndex = 0;

    // Tracks direction down / up
    bool down = true;

    for (int index = 0; index < s.Length; index++)
    {

        strstr[strstrIndex] += s[index];

        if (down)
            strstrIndex++;
        else
            strstrIndex--;

        // If reached down completely
        if (strstrIndex == nRows)
        {
            strstrIndex -= 2;
            down = false;
        }

        // If reached up completely
        if (strstrIndex == -1)
        {
            strstrIndex += 2;
            down = true;
        }
    }

    // Append all the strings and return
    for (int index = 0; index < nRows; index++)
        result += strstr[index];

    return result;
}

No comments:

Post a Comment