55ms JAVA code O(n): easy to understand by using multi-StringBuilder


  • 0
    C

    I regard every 2 column as a part. So every part has 2*numRows-2 elements. mod = i mod (2*numRows-2) will get the relative position of char.

    Main Thought:
    1.We can get the chars in the 1st and last line, and store them in 2 StringBuilder.
    2.Build another (numRows - 2) numRows for store the other lines.
    3.the 1st line: mod == 0, the last line: mod == numRows - 1.

    public String convert(String s, int numRows) {
            if (numRows == 1 || numRows >= s.length()) {
                return s;
            }
            StringBuilder pre = new StringBuilder();  // storing the 1st line
            StringBuilder[] mid = new StringBuilder[numRows - 2]; // mid[i] storing the ith line
            StringBuilder aft = new StringBuilder();  // storing the last line
            int divider = (numRows - 1) * 2;
            for (int i = 0; i < s.length(); i++) {
                int mod = i % divider;
    
                if (mod == 0) {
                    pre.append(s.charAt(i));
                } else if (mod == numRows - 1) {
                    aft.append(s.charAt(i));
                } else {
                    int index = mod < numRows - 1? mod - 1 : divider - mod - 1;
                    if (mid[index] == null) {
                        mid[index] = new StringBuilder();
                    }
                    mid[index].append(s.charAt(i));
                }
            }
    
            for (int i = 0; i < mid.length; i++) {
                pre.append(mid[i]);
            }
            return pre.append(aft).toString();
        }
    

Log in to reply
 

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