# Time Limit Exceeded. How to improve???

• ``````public class Solution {
public int minCut(String s)
{
int len = s.length();
int[] dp = new int[len];
for (int i = 0; i < len; i++)
if (isPal(s.substring(0, i + 1)))
dp[i] = 0;
else
dp[i] = Integer.MAX_VALUE;
for (int i = 0; i < len; i++)
{
if (dp[i] == 0)
continue;

for (int j = 0; j < i; j++)
{
if (isPal(s.substring(j + 1, i + 1)))
if (dp[i] > dp[j] + 1)
dp[i] = dp[j] + 1;
}
}
return dp[len - 1];
}

private boolean isPal(String s)
{
int len = s.length();
for (int i = 0; i < len; i++) {
if (s.charAt(i) != s.charAt(len - 1 - i))
return false;
}
return true;
}}
``````

This is my code. dp[i] = MIN(dp[j] + 1) where ( j < i && isPal(s[j+1, i+1]) ).
In eclipse, it spend about 1-2 seconds, but in leetcode it says "Time Limit Exceeded".

• 1-2 seconds must be a TLE. No solution was allowed to have 1000ms in leetcode. Your solution is O(n^3) time complexity. So it must have some trouble to pass.

Take a look of my solution. It uses a matrix to store the information of whether or not a substring is a palindrome.

``````public class Solution {

public int minCut(String s) {

if (s==null||s.length()==0) return 0;

int length=s.length();

boolean[][] palindrome= new boolean[length][length];

for (int i=0;i<length;i++)
Arrays.fill(palindrome[i],false);

int[] results = new int[length];

for (int start=length-1;start>=0;start--){
results[start]=length-start-1;
for (int end=start;end<length;end++){
if (s.charAt(start)==s.charAt(end)){
if (end-start<2)
palindrome[start][end]=true;
else
palindrome[start][end]=palindrome[start+1][end-1];
}
if (palindrome[start][end])
if (end==length-1)
results[start]=0;
else
results[start]=Math.min(results[start],results[end+1]+1);
}
}
return results[0];
``````

}
}

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