Time limit exceeding. Better solution?


  • 0
    A

    Hi,
    I tried the below code for the ZigZag conversion. I feel that it runs with O(n) complexity. Still I get time limit exceeding. Is there a O(logn) or better solution? Any suggestions?

        public String convert(String s, int nRows) {
            if (nRows == 1) return s;
        	Character [][] chararray = new Character[nRows][1000];
        	String retString = "";
        	int len = 0;
        	int i = 0,j = 0;
        	while(len < s.length()){
    			if(len >= s.length()){
    				break;
    			}	
        		chararray[i][j] = s.charAt(len);
        		i++;
        		len++;
    
        		if(i == nRows){
        			i--;
        			while(i > 0){
        				if(len >= s.length()){
        					break;
        				}
        				i--;
        				j++;
        				chararray[i][j] = s.charAt(len);
        				len++;
        			}
        			i++;
        		}
        	}
    
    	    	for(int k = 0 ; k < nRows; k++){
        	    		for(int l = 0; l <= j; l++){
        				if(chararray[k][l] != null){
        					retString += chararray[k][l];
        				}
        			}
        		}
        	return retString;
    }

  • 0
    S

    I think your j is not run as expected. It will grow large when doing the last for loop.


  • 4
    L

    While I am not certain of the correctness of your algorithm, I still have a few comments:

    1. There is no need of creating the huge matrix chararray. There exists a linear time, constant space algorithm. I think this is your main bottleneck.
    2. You have defined the matrix chararray by Character[][] chararray. You should use primitive types whenever possible, i.e., char[][] chararray. You are loosing a lot of time because of that. Creating objects is really costly. Go read about autoboxing in Java.
    3. Again, creating objects in Java is really expensive, and lines like that one retString += chararray[k][l]; are performance killers. Every time you append one character to retString, you are recreating a whole new String object. Go read about the object StringBuilder in Java. It has been designed for exactly this kind of situations.

    You should focus on finding a better algorithm. Try, as an exercise, to first design an algorithm that creates only the string of the letter of the first row. For s = "PAYPALISHIRING" and nRows = 3, your algorithm should return "PAHN".


  • 0
    A

    Thanks a lot for your inputs Loick! I'm really grateful for point 2!


  • 3
    R
    class Solution{
    public:
        string convert(string s, int nRows) {
        	if(nRows < 2 || s.length() <= nRows) return s;
        	string ret = "";
        	for(int row=0; row<nRows; row++){
        		if(row == 0 || row == nRows-1){
        			int step = 2*nRows-2;
        			int index = row;
        			while(index < s.length()){
        				ret.push_back(s[index]);
        				index += step;
        			}
        		}else{
        			int step = 2*nRows-2;
        			int index = row;
        			while(index < s.length()){
        				ret.push_back(s[index]);
        				int zig_index = index + (step - 2*row);
        				if(zig_index < s.length()) ret.push_back(s[zig_index]);
        				index += step;
        			}
        		}
        	}
        	return ret;
        }
    };
    

    Here is my O(n) solution for your reference.

    1. Each row starts exactly at index = row.

    2. There is no zigzag elements in the first and last row. The step is fixed at step = 2*nRows-2.

    3. For other rows, the step for the full column is that same as step = 2nRows-2 and the step for the middle zigzag element is step-2row.


  • 4
    L

    Let's use simple formula to do this.

    Suppose you have N rows, indexing from 0 to N-1. For each char s[i] in s, where 0<i<s.size(), you need to put the char in the position:

      i=                            example:
    ||  0           2(N-1)              ||       P   A
    \/  1        .  2(N-1)+1            \/       A P L
        .     N+1   .                            Y
        .   N       .
        N-1         3(N-1)
    

    i.e. for the example in the question, N=3.

    let's say we use a string array of length N, let's call it v, to store the chars of each row. What we need to do is just to come up with a function y=f(i) such that:

    f[0]         f[2(N-1)]            = 0
    f[1]       .                      = 1
    .        f[N+1]                   = .
    .     f[N]                        = .
    f[N-1]                            = N-1
    

    Then we just need to v[f[i]] += s[i] for each s[i].

    And then the problem is how to write the function f.

    If you realize the function is nothing more than

          |
     r-1  |      /\            /\
          |    /    \        /    \
          |  /        \    /       \
          |/            \/           \
     0    |----------------------------------
          0     r-1   2(r-1)  3(r-1)  4(r-1)
    

    You can program it like

        for(int i = 0, v_index=0; i < s.size(); i++) {
          int x = i % (2*n-2);
          if (x<=n-1){
            v_index = x;
          } else {
            v_index = 2*n-2-x;
          }
          v[v_index] += s[i];
        }

  • 0
    T
    public String convert(String s, int nRows) {
    	List<StringBuilder> ls = new ArrayList<StringBuilder>();
    	for (int i = 0; i < nRows; i++) {
    		ls.add(new StringBuilder());
    	}
    	char[] arr = s.toCharArray();
    	if(nRows <= 1) return s;
    	for (int i = 0; i < arr.length; i++) {
    		int mod = 2 * nRows - 2;
    		int index = i % mod;
    		int line = -1;
    		if (index >= 0 && index <= nRows - 1) {
    			line = index;
    		} else {
    			line = mod - index;
    		}
    		StringBuilder sb = ls.get(line);
    		sb.append(arr[i]);
    	}
    
    	String result = "";
    	for (StringBuilder builder : ls) {
    		result += builder.toString();
    	}
    	return result;
    }

Log in to reply
 

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