Python code TLE for case "a".

```
class Solution:
def palindrome(self, s, left, right):
for i in xrange((right - left) / 2):
if s[left + i] != s[right - 1 - i]:
return False
return True
# @param s, a string
# @return a list of lists of string
def minCut(self, s):
if len(s) == 1:
return 0
pali = [99999 for i in xrange(len(s) + 1)]
pali[0] = -1
for i in xrange(1, len(s) + 1):
for j in xrange(i - 1, -1, -1):
if pali[j] + 1 < pali[i] and self.palindrome(s, j, i):
pali[i] = pali[j] + 1
return pali[-1]
```

Even I put a

```
if len(s) == 1:
return 0
```

there.

And translated Java code is accepted.

```
public class Solution {
boolean palindrome(String s, int left, int right)
{
int l = (right - left) / 2;
for(int i = 0; i < l; i++){
if (s.charAt(left + i) != s.charAt(right - 1 - i))
return false;
}
return true;
}
public int minCut(String s) {
int len = s.length();
Integer[] pali = new Integer[len + 1];
Arrays.fill(pali, 99999);
pali[0] = -1;
for(int i = 1; i < len + 1; i++)
{
for(int j = i - 1; j > -1 ; j--)
{
if (pali[j] + 1 < pali[i] && palindrome(s, j, i)){
pali[i] = pali[j] + 1;
}
}
}
return pali[len];
}
}
```