O(n) time, O(1) Space Java Solution. Beats 90%


  • 0
    J

    My code is a bit messy, I apologize for that.

    There are two cases here:

    1. The next character in the original string is on a row above the current row.
    2. The next character in the original string is on a row below the original string.

    The first characters on every row would be the characters in the corresponding positions on the original string. For example: abcdef with numRows=3 will have a,b,c as the first characters on the first three rows.

    For the first case the next character on its row would be at a position 2*(currentRow-1) from the position of the current character in the original string. Similarly, for the second case the position would be 2*(numRows-currentRow).

    public class Solution {
        public String convert(String s, int numRows) {
            
            if(numRows==1 || numRows>s.length()) return s;
            
            StringBuilder sb = new StringBuilder();
            int rowCount=1,curIndex=0, count=0;
            
            while(rowCount<=numRows){
    
                if(curIndex>=s.length()){
                    rowCount++;
                    curIndex=rowCount-1;
                    count=0;
                    continue;
                }
                
                
                sb.append(s.charAt(curIndex));
                count++;
                
                if(rowCount!=1 && rowCount!=numRows)
                    curIndex+= (count%2==0) ? (2*(rowCount-1)) :(2*(numRows-rowCount));
                    
                else curIndex+= (rowCount==numRows) ? (2*(rowCount-1)) :(2*(numRows-rowCount));
                
            }
            
            
            return sb.toString();
        }
    }
    

Log in to reply
 

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