public static int minCut(String s) {
        if (s==null||s.length()==0||s.length() == 1||isPalindrome(s)) {//if is Palindrome return true directly
            return 0;
        } else {
            if (minCutMap.get(s) != null) {
                return minCutMap.get(s);
            }
            Integer min = null;
            for (int start = 0; start < s.length(); start++) {
                if (isPalindrome(s.substring(0, start + 1))) {
                    int cut = 1 + minCut(s.substring(start + 1, s.length()));
                    if (min == null || cut < min) {
                        min = cut;
                    }
                }
            }
            minCutMap.put(s, min);
            return min;
        }
    }