One-pass solution with O(n) space complexity


  • 0
    C

    My thought:

    Allocate each character of the string to string arrays by using a boolean flag to denote the direction.

    But at last, I used a string "result" to return the whole string, which take additional O(n) time and space complexity. I think this could be done better.

    string convert(string s, int nRows) {
            if( nRows < 1 )     return "";
            else if( 1 == nRows )    return s;
            
            string *strings = new string[nRows];
            for( int i=0; i<nRows; i++ ) {
                strings[i] = "";
            }
            
            bool isDownward = true;
            
            int i=0;
            while( '\0'!=s[i] ) {
                if( isDownward ) {
                    for( int j=0; j<nRows && '\0'!=s[i]; j++ )
                        strings[j] += s[i++];
                        
                    isDownward = false;
                }
                else {
                    for( int j=nRows-2; j>0 && '\0'!=s[i]; j-- )
                        strings[j] += s[i++];
                        
                    isDownward = true;
                }
            }
            
            string result="";
            for( int j=0; j<nRows; j++ )
                result += strings[j];
                
            return result;
        }

Log in to reply
 

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