Two ways of O(n) solutions one follows the order of input string and other follows the order of output string


  • 26
    V

    Both the algorithms are of O(n) time complexity as every character in the input string is traversed only once.
    In the first version of algorithm, the output string's string buffer get populated based on the output string order i.e, string builder gets populated incrementally from 0 to size-1.

    0             6            12             18
    
    1       5     7      11    13       17    19
    
    2    4        8  10        14  16         20
    
    3             9            15             21 
    

    In the above sample case the number of rows is 4, when the first iteration is completed the locations 0,1,2,3 of the string builder gets filled with the locations 0,6,12,18 of the input string it goes on further for other three rows.

    public class Solution {
        public String convert(String s, int nRows) {
            if (nRows == 1)
                return s;
            StringBuilder strBuilder = new StringBuilder();
            int borderRowStep = 2 * nRows - 2;
            for (int i = 0; i < nRows; i++) {
                if (i == 0 || i == nRows - 1) {
                    for (int j = i; j < s.length(); j = j + borderRowStep) {
                        strBuilder.append(s.charAt(j));
                    }
                } else {
                    int j = i;
                    boolean flag = true;
                    int insideRowLargeStep = 2 * (nRows - 1 - i);
                    int insideRowSmallStep = borderRowStep - insideRowLargeStep;
                    while (j < s.length()) {
                       strBuilder.append(s.charAt(j));
                        if (flag)
                            j = j + insideRowLargeStep;
                        else
                            j = j + insideRowSmallStep;
                        flag = !flag;
                    }
                }
            }
            return strBuilder.toString();
        
    }
    }
    

    In the second version of algorithm string buffer is filled in the order of input string i.e, the string buffer gets filled in the zig zag order, when the first iteration of the outer while loop completes the locations 0,5,11,17 in string builder gets filled with the locations 0,1,2,3, from the input string

    class Solution{
    public String convert(String s, int nRows) {
        char[] c = s.toCharArray();
        int len = c.length;
        StringBuffer[] sb = new StringBuffer[nRows];
        for (int z=0; z < sb.length; z++) sb[z] = new StringBuffer();
        int k=0;
        while (k < len) {
            for (int zigZagIndex = 0; zigZagIndex < nRows && k < len; zigZagIndex++) // vertically down
                sb[zigZagIndex].append(c[k++]);
            for (int zigZagIndex = nRows-2; zigZagIndex >= 1 && k < len; zigZagIndex--) // obliquely up
                sb[zigZagIndex].append(c[k++]);
        }
        for (int index = 1; index < sb.length; index++)
            sb[0].append(sb[index]);
        return sb[0].toString();
    }
    }

  • 0
    S

    here is my answer. use StringBuilder[]:

      public  String convert(String s, int nRows) {
    	if (s.length() == 0 || nRows <=1) return s;
    	boolean flag = true;
    	int state = 0;
    	StringBuilder[] sbs = new StringBuilder[nRows];
    	for (int i = 0; i < nRows; i++)
    		sbs[i] = new StringBuilder();
    	for (int i = 0; i < s.length(); i++){
    		sbs[state].append(s.charAt(i));
    		if ((state == nRows - 1 && flag) || (state == 0 && !flag))
    			flag = !flag;
    		state = getNext(state,flag);
    	}
    	for (int i =1; i < nRows; i++){
    		sbs[0].append(sbs[i]);
    	}
    	return sbs[0].toString();
    }
    
    private int getNext(int state, boolean flag){
    	return flag ? state +1 : state - 1;
    }

Log in to reply
 

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