I think my solution is perfect,why is the runtime so long?


  • 0
    Z

    I think my solution is perfect,why runtime is so long? i have no idea for it.

                int sLen = s.length();
    	if(sLen==0)
    		return "";
    	int d = 0;
    	int[] arrayList = new int[2];
    	int dpI = 0;
    	while (d < sLen) {
    		while (d < sLen && s.charAt(d++) != s.charAt(0))
    			;
    		if(d==sLen){
    		   if(s.charAt(d-1) != s.charAt(0))
                break;				
    		}
    		if(dpI>=arrayList.length-1){
    			int[] array = new int[arrayList.length<<1];
    			System.arraycopy(arrayList, 0,array,0, arrayList.length);
    			arrayList =array;
    		}
    		//System.out.print("---"+(d-1));
    		arrayList[dpI++] = d-1;
    	}
    	
    	
    	for (int i = dpI-1; i >= 0; i--) {
    		int j = arrayList[i]-1;
    		//System.out.println(j);
    		if (j == -1) {
    			// abcd
    			int t = 1;
    			// StringBuilder sb = new StringBuilder(s);
    			//System.out.println(sLen);
    			char[] c = new char[(sLen << 1) - 1];
    			while (t < sLen) {
    				// sb.insert(0, s.charAt(t));
    				c[sLen - t - 1] = s.charAt(t);
    				t++;
    			}
    			s.getChars(0, sLen, c, sLen - 1);
    			return new String(c);
    		} else {
    			int k = 1;
    			int o = j + 1;
    			while (j >= 0 && k <= sLen - 1 && j >= k
    					&& s.charAt(j--) == s.charAt(k++))
    				;
    			if (s.charAt(j) != s.charAt(k))
    				continue;
    			if (k > j) {
    				if (o == sLen - 1) {
    					// 回文
    					return s;
    				} else {
    					// StringBuilder sb = new StringBuilder(s);
    					int des = sLen - o - 1;
    					int len = des - 1;
    					// System.out.println("--->" + len);
    					char[] c = new char[sLen + des];
    					for (int y = o + 1; y < sLen; y++) {
    						c[len--] = s.charAt(y);
    						// System.out.println(y);
    						// System.out.println(s.charAt(y));
    						// sb.insert(0, s.charAt(y));
    					}
    					// System.out.println("des---->" + des + "--" + c.length
    					// + "--" + s.length());
    					s.getChars(0, sLen, c, des);
    					return new String(c);
    				}
    			}
    		}
    
    	}
    
    	return s;

Log in to reply
 

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