Java: O(2n) time, O(n) space


  • 0
    E

    The idea is simple: scan the input string from left to right, spreading its characters in matrix.
    Then traverse the matrix level by level, building the result.

    Implementation:

    public class Solution {
        public String convert(String s, int numRows) {
            List<List<Character>> matrix = new ArrayList<>();
            int i = 0;
            while (i < s.length()) {
                for (int level = 0; level < numRows && i < s.length(); i++, level++) {
                    if (matrix.size() == level) matrix.add(new ArrayList<Character>());
                    matrix.get(level).add(s.charAt(i));
                }
                for (int level = numRows - 2; level > 0 && i < s.length(); level--, i++) {
                    matrix.get(level).add(s.charAt(i));
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int level = 0; level < matrix.size(); level++) {
                for (char c : matrix.get(level)) sb.append(c);
            }
            return sb.toString();
        }
    }

Log in to reply
 

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