Java O(n^2) solution, I want to know if it's possible to use just one double loop.


  • 1
    J
    public int minCut(String s) {
        int len = s.length();
        if(len == 1) return 0;
        char[] array = s.toCharArray();
        boolean[][] cuts = new boolean[len][len];
        int[] res = new int[len];
        cuts[0][0] = true;
        for(int i=1; i<len; i++){
            cuts[i][i] = true;
            cuts[i][i-1] = true;
        }
        for(int i=1; i<len; i++){
            for(int j=0; j<len-i;j++) {
                if(array[j] == array[j+i] && cuts[j+1][j+i-1]) {
                    cuts[j][j+i] = true;
                } else {
                	cuts[j][j+i] = false;
                }
            }
        }
        for(int i=0; i<len; i++) {
        	int min = i;
        	for(int j=0; j<=i; j++) {
        		if(cuts[j][i]) {
        			min = Math.min(min, j == 0 ? 0 : res[j-1] + 1);
        		}
        	}
        	res[i] = min;
        }
        return res[len-1];
    }
    

    First create a two dimensional array that cuts[i][j] means whether string from i to j can form a Palindrome. Then use this cuts array to determine result. The logic is: if string from j to i can form a Palindrome, then we can use (the smallest) res[j-1]+1 to represent res[i].


Log in to reply
 

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