If you are confused with zigzag pattern,come and see!


  • 251
    /*n=numRows
    Δ=2n-2    1                           2n-1                         4n-3
    Δ=        2                     2n-2  2n                    4n-4   4n-2
    Δ=        3               2n-3        2n+1              4n-5       .
    Δ=        .           .               .               .            .
    Δ=        .       n+2                 .           3n               .
    Δ=        n-1 n+1                     3n-3    3n-1                 5n-5
    Δ=2n-2    n                           3n-2                         5n-4
    */
    

    that's the zigzag pattern the question asked!
    Be careful with nR=1 && nR=2









    my 16ms code in c++:

    class Solution {
    public:
        string convert(string s, int numRows) {
            string result="";
            if(numRows==1)
    			return s;
            int step1,step2;
            int len=s.size();
            for(int i=0;i<numRows;++i){
                step1=(numRows-i-1)*2;
                step2=(i)*2;
                int pos=i;
                if(pos<len)
                    result+=s.at(pos);
                while(1){
                    pos+=step1;
                    if(pos>=len)
                        break;
    				if(step1)
    					result+=s.at(pos);
                    pos+=step2;
                    if(pos>=len)
                        break;
    				if(step2)
    					result+=s.at(pos);
                }
            }
            return result;
        }
    };

  • 33
    F

    Good explanation for those who don't know what zigzag string is, thanks!


  • 5
    Z

    Thanks a lot for ZigZag explanation, I really don't get the idea from the problem. Thanks a lot!


  • 0
    Z

    Thanks a lot. The question description was not clear at all and the example is kind of special, which does not help much.


  • 2
    L

    Also go check the graphs in this blog: https://segmentfault.com/a/1190000005751185, it helps a lot to think Zigzag as a Sinusoidal(i.e. sine wave).


  • 12

    Thanks for your explanation. I have a more concise C++ solution

    class Solution {
    public:
        string convert(string s, int numRows) {
            if( numRows==1 ) return s;
            vector<string> res(numRows);
            int row=0;
            int increase=-1;
            for(int i=0; i<s.size(); ++i){
                // every time at turning point, we change the increase direction
                if(i%(numRows-1)==0) increase *= -1;
                res[row].push_back(s[i]);
                row += increase;
            }
            string ret;
            for(const auto& str:res){
                ret += str;
            }
            return ret;
        }
    };
    

  • 0
    X

    @yanchao_hust Right and easy to understand, but slower. 36ms in total.


  • 0
    U

    My 9 ms Simple Java Solution

    public String convert(String s, int numRows) {
            //actually to find the pattern of indexes
            //special conditions numRows:1
            if (numRows == 1) return s;
            int offset = 2 * numRows - 2;
            StringBuffer result = new StringBuffer();
            for (int i = 0; i < numRows; i ++) {
                //first and last row increase a model
                //zigzag pattern is an upside down N pattern
                for (int j = 0; j*offset + i < s.length(); j ++) {
                    result.append(s.charAt(j*offset + i));
                    if (i != 0 && i != numRows - 1 && (j+1)*offset - i < s.length()) result.append(s.charAt((j+1)*offset - i));
                }
            }
            return result.toString();
        }
    

  • 4
    S

    5ms solution...

    public String convert(String str, int R) {
        if (R == 1) return str;
    
        char[] s = str.toCharArray();
        char[] t = new char[s.length];
    
        for (int i = 0, len = 0; i < R; i++) {
            for (int j = 0, k = i; k < s.length; j++) {
                t[len++] = s[k];
                k += ((i == 0 || j % 2 == 0) && i != R - 1 ? 2 * (R - i - 1) : 2 * i);
            }
        }
    
        return new String(t);
    }

  • 2
    S

    Same idea but more short & simple c++ solution

    class Solution {
    public:
        string convert(string s, int numRows) {
            string res="";
            if(numRows==1) return s;
            for(int i=0; i < numRows; i++){
                for(int j=0, k=i; k < s.size(); j++){
                    res += s[k];
                    k += ((i==0 || (j%2==0)) && (i!= numRows-1) )? 2*(numRows-i-1) : 2*i;
                }
            }
            return res;
        }
    };```

  • 0
    T

    Thanks for the explanation about the zigzag!


  • 1
    S

    @s961206
    Very slick solution, could you please elaborate regarding the increment of k?

    k += ((i==0 || (j%2==0)) && (i!= numRows-1) )? 2*(numRows-i-1) : 2*i;


  • 0
    S

    @HelloKenLee Straightforward work!


  • 0

    @HelloKenLee I love you!


  • 0
    M

    Thank you kindly for the explanation, made the problem clear and simple!


  • 0
    L

    concise code with thought-provoking explanation!


  • 0
    A

    Share my Java solution with the same idea but maybe a little bit concise.

    1. interval starts from 2 * numRows - 2 and decrease by 2. (As same as the step1 in @HelloKenLee solution).
    2. In the while loop, i is 0 means we are in the first row and interval is 0 means we reach the last row. In both cases, we just need to avoid appending repeated characters. Otherwise, we append 2 characters.
    public String convert(String s, int numRows) {
            if(numRows == 1)    return s;
            StringBuilder b = new StringBuilder();
            int interval = 2 * numRows - 2;
            int n = s.length();
            for(int i = 0; i < numRows; i++){
                int j = i;
                while(j < n){
                    if(interval != 0)
                        b.append(s.charAt(j));
                    j += interval;
                    if(i != 0 && j < n)
                        b.append(s.charAt(j));
                    j += 2 * i;
                }
                interval -= 2;
            }
            return b.toString();
        }
    

  • 0
    O

    Thanks a lot !


  • 0
    S

    Thanks for explaining the ZigZag. The questions fail to clearly define the zigzag pattern. So, I had to make a lot of assumptions and keep trying different patterns. Thanks for making it easy.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.