JAVA---------Easy Version To Understand!!!!!


  • 0
    H
    public static int minCut(String s) {
    	if (s == null | s.length() == 0)
    		return 0;
    	int len = s.length();
    	int[][] dp = new int[len][len];
    	int[] cut = new int[len];
    	for (int i = 0; i < len; i++)
    		for (int j = 0; j < len; j++)
    			dp[i][j] = 0;
    	for (int j = 0; j < len; j++) {
    		cut[j] = Integer.MAX_VALUE;
    		for (int i = 0; i <= j; i++) {
    			if ((s.charAt(i) == s.charAt(j) && j - i >= 2 && dp[i + 1][j - 1] == 1)
    					|| (s.charAt(i) == s.charAt(j) && j - i <= 1)) {
    				dp[i][j] = 1;
    				if (i == 0) {
    					cut[j] = 0;
    				} else {
    					cut[j] = Integer.min(cut[j], 1 + cut[i - 1]);
    				}
    			}
    		}
    	}
    	return cut[len - 1];
    }

Log in to reply
 

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