Longest Palindromic Substring lime out


  • 0

    Hi All,
    I basically have two exactly the same solution for the longest Palindromic Substring, one is Java, one is C++. Can someone tell me why the C++ one works well while the Java one is time out for the last test case????? Thanks a lot!

    JAVA

    public class Solution {
        public String longestPalindrome(String s) {
              int n = s.length();
      int longestBegin = 0;
      int maxLen = 1;
      int table[][] = new int[1000][1000];
      for (int i = 0; i < n; i++) {
        table[i][i] = 1;
      }
      for (int i = 0; i < n-1; i++) {
        if (s.charAt(i) == s.charAt(i+1)) {
          table[i][i+1] = 1;
          longestBegin = i;
          maxLen = 2;
        }
      }
      for (int len = 3; len <= n; len++) {
        for (int i = 0; i < n-len+1; i++) {
          int j = i+len-1;
          if (s.charAt(i) == s.charAt(j) && table[i+1][j-1]==1) {
            table[i][j] = 1;
            longestBegin = i;
            maxLen = len;
          }
        }
      }
      return s.substring(longestBegin, longestBegin + maxLen - 1);
            
        }
            
        
    }
    

    C++

    class Solution {
    public:
        string longestPalindrome(string s) {
              int n = s.length();
      int longestBegin = 0;
      int maxLen = 1;
      bool table[1000][1000] = {false};
      for (int i = 0; i < n; i++) {
        table[i][i] = true;
      }
      for (int i = 0; i < n-1; i++) {
        if (s[i] == s[i+1]) {
          table[i][i+1] = true;
          longestBegin = i;
          maxLen = 2;
        }
      }
      for (int len = 3; len <= n; len++) {
        for (int i = 0; i < n-len+1; i++) {
          int j = i+len-1;
          if (s[i] == s[j] && table[i+1][j-1]) {
            table[i][j] = true;
            longestBegin = i;
            maxLen = len;
          }
        }
      }
      return s.substr(longestBegin, maxLen);
            
        }
    };

  • 0
    S
    public class Solution {
    public String longestPalindrome(String s) {
    String ss="";
    	for (int i = 0, num = s.length(); i < num; i++) {
    		for (int j = 0; j <=i; j++) {
    			ss = s.substring(j, num-i+j);
     			if ((new StringBuffer(ss)).reverse().toString().equals(ss)) {
    				return ss;
    			}
    		}
    	}
    	return ss;
    }}
    

    Anyone tell me why my code fails to pass the time limit testing? thanks a lot


Log in to reply
 

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