Easy Solution using Formula in C++


  • 0
    N

    Let : r = numRows
    The concept is for any index, the next char differs by
    r + ( r - 2) if we don't consider the diagonal
    characters.

        For the 0th and r - 1 index, since there is no
        corresponding intermediate diagonal characer
        they always differ by r + ( r - 2 ).
        
        For every index inbetween, it differs on how close
        it is to the bot or how close it is to the top.
        
        By using  ind % ( r - 1 ). We can find out how
        close it is to one of the ends.
        
        We multiply it by 2 because for every value that
        is prior to the current index since one of the
        previous ends, we will have to traverse a value
        in the diagonal to reach the next character.
        As in if there are 2 values before an index from
        top, then there are 2 values it needs to traverse
        in the diagonal before reaching its next char.
        
        Subtracting 2 * ( ind % (r - 1) ) from r + (r - 2),
        will give us the next value.
    
    class Solution {
    public:
        string convert(string s, int numRows) {
            
            if ( numRows <= 1 || numRows > s.size() )
                return s;
            
            std::string result = "";
            int r = numRows;
            int nextPos = r + ( r - 2);
    
            for (int i = 0; i < r; i++) {
                int index = i;
                while ( index < s.size() ) {  
                    result += s[index];
                    int incr = nextPos - 2 * ( index % ( r - 1));
                    index += incr;
                }
            }
            
            return result;
        }
    };
    

Log in to reply
 

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