O(s.length()) Java Algorithm


  • 0
    W

    calculate each step length you need to take at each row, and put the corresponding char from string into char array.
    Add the suitable step length to the string index in order to find next char value.
    The code is simple.

        public String convert(String s, int numRows) {
            if (numRows == 1) return s;
            char[] result = new char[s.length()];
            int resultIdx = 0;
            for (int curRow = 0; curRow < numRows; ++curRow) {
                int stepLen1 = (numRows - 1 - curRow) << 1;
                int stepLen2 = curRow << 1;
                if (stepLen1 < 1) stepLen1 = stepLen2;
                if (stepLen2 < 1) stepLen2 = stepLen1;
                for (int strIdx = curRow, step = 1; strIdx < s.length(); ++step) {
                    result[resultIdx++] = s.charAt(strIdx);
                    strIdx += step % 2 == 0 ? stepLen2 : stepLen1;
                }
            }
            return String.valueOf(result);
        }
    

Log in to reply
 

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