28ms JAVA DP Top-Down


  • 1
    W
    public class Solution {
        int[][] panMap;
        int[] map;
        
        public int minCut(String s) {
            panMap = new int[s.length()][s.length()];
            map = new int[s.length() + 1];
            Arrays.fill(map, Integer.MAX_VALUE);
            map[s.length()] = 0;
            return minCut(s, 0) - 1;
        }
        
        private int minCut(String s, int start) {
            if (map[start] != Integer.MAX_VALUE) return map[start];
            for (int i = start; i < s.length(); i++) {
                if (isPan(s, start, i)) {
                    map[start] = Math.min(map[start], 1 + minCut(s, i + 1));
                }
            }
            return map[start];
        }
        
        private boolean isPan(String s, int start, int end) {
            if (start == end) return true;
            if (end == start - 1 && s.charAt(start) == s.charAt(end)) return true;
            if (panMap[start][end] != 0) return panMap[start][end] == 1 ? true : false;
    
            if (s.charAt(start) == s.charAt(end)) {
                panMap[start][end] = isPan(s, start + 1, end - 1) ? 1 : -1;
            }
            return panMap[start][end] == 1 ? true : false;
        }
    }

Log in to reply
 

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