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


  • 271
    /*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;
        }
    };

  • 35
    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;


  • 1
    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.


  • 0
    L

    thanks~ explantion help me to understand the problem


Log in to reply
 

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