Programming with Passion Algorithms, Mobile Development, Robotics

Sunday, April 30, 2017

LeetCode (Algorithms#6) ‒ ZigZag Conversion

Problem

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:

P   A   H   N
A P L S I I G
Y   I   R

Examples:

convert("PAYPALISHIRING",3) should return "PAHNAPLSIIGYIR"

Solution

The problem is essentially of remapping indices to the known pattern. Given the number rows n in the zigzag, it is easy to find that the number of characters in a single zigzag is 2n-2. Additionally, there is a one to one correspondence between the indices in each ordering, so with information of the zigzag size, there should be no problem traversing through and reassigning each character's indices in O(n).

Time complexity: O(n)
Space complexity: O(n)
Percentile: 98.12%

public String convert(String s, int nRows) {
    if (s==null || s.length()==0) return "";
    if (nRows < 2) return s;
    
    int N = s.length();
    int n = 2*nRows-2;
    
    int idx = 0;
    StringBuilder sb = new StringBuilder();

    for (int i=0; i<nRows; i++) {
        for (int j=i; j<N; j+=n) {
            sb.append(s.charAt(j));
            if (i>0 && i<nRows-1 && j+n-2*i<N) 
                sb.append(s.charAt(j+n-2*i));
        }
    }
    
    return sb.toString();
}

No comments:

Post a Comment