Palindrome Partitioning II

제목 설명:
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
예 를 들 어, given s = "aab", Return 1 since the palindrome partitioning ["aa","b"] could be production using 1 cut. 첫 번 째 아 이 디 어 는 dfs 입 니 다. 이렇게 쓰 면 시간 이 초 과 됩 니 다.

public class Solution {
    Map<String,Integer> map=new HashMap<String,Integer>();
        
    public int minCut(String s) {
        int min=Integer.MAX_VALUE;
        if(isPalindrome(s))
            return 0;
        for(int i=0;i<s.length()-1;i++){
            String substr=s.substring(0,i+1);
            if(set.contains(substr)){
                int cutnum=minCut(s.substring(i+1));
                min=cutnum+1<min?cutnum+1:min;
            }else{
                if(isPalindrome(substr)){
                    set.add(substr);
                    int cutnum=minCut(s.substring(i+1));
                    min=cutnum+1<min?cutnum+1:min;
                }else{
                    int cutnum=minCut(s.substring(0,i+1))+minCut(s.substring(i+1,s.length()))+1;
                    min=cutnum+1<min?cutnum+1:min;
                }
            }
        }
        return min;
    }
}

나중에 비망록 을 넣 었 습 니 다. 그리고 여기 서 substring 함 수 를 호출 할 때마다 시간 이 낭비 된다 고 생각 했 습 니 다. 그래서 저 는 char [] 로 바 뀌 었 습 니 다. 속도 가 많이 빨 라 졌 지만 시간 이 초과 되 었 습 니 다. WTF!

public class Solution {
    Map<String,Integer> map=new HashMap<String,Integer>();
    
    public int minCut(String s) {
        return getMinCut(s.toCharArray(), 0,s.length()-1);
    }
	
	public int getMinCut(char[] chars,int left,int right){
		String str=new String(chars, left, chars.length-left);
		if(map.containsKey(str))
			return map.get(str);
		if(isPalindrome(chars,left,right))
        	return 0;
		int min=Integer.MAX_VALUE;
		for(int i=left;i<right;i++){
        	String substr=new String(chars, left, i-left+1);
        	if(map.containsKey(substr)){
        		int leftCut=map.get(substr);
        		int rightCut=getMinCut(chars,i+1,right);
        		min=leftCut+rightCut+1<min?leftCut+rightCut+1:min;
        	}else{
        		if(isPalindrome(chars,left,i)){
        			map.put(substr,0);
        			int rightCut=getMinCut(chars,i+1,right);
            		min=rightCut+1<min?rightCut+1:min;
        		}else{
        			int leftCut=getMinCut(chars,left,i);//       i+1
        			int rightCut=getMinCut(chars,i+1,right);
        			min=leftCut+rightCut+1<min?leftCut+rightCut+1:min;
        		}
        	}
        }
		map.put(str, min);
        return min;
	}
	
	private boolean isPalindrome(char[] chars,int left,int right){
		while(left<right){
			if(chars[left]==chars[right]){
				left++;right--;
			}else{
				return false;
			}
		}
		return true;
	}
}

이 문제 의 정확 한 위 에서 아래로 dfp 알고리즘:
여 기 는 답문 수 여 부 를 판단 할 때 바로 panMap 에서 찾 습 니 다.

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++) {
            //   start==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;
    }
}

아래 에서 위로 dp 알고리즘:
This can be solved by two points:

cut[i] is the minimum of cut[j - 1] + 1 (j <= i) , if [j, i] is palindrome.

If [j, i] is palindrome, [j + 1, i - 1] is palindrome, and c[j] == c[i] .

public class Solution {
    public int minCut(String s) {
        char[] c = s.toCharArray();
        int n = c.length;
        int[] cut = new int[n];
        boolean[][] pal = new boolean[n][n];
    
        for(int i = 0; i < n; i++) {
            //   min    
            int min = i;
            for(int j = 0; j <= i; j++) {
                if(c[j] == c[i] && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
                    pal[j][i] = true;  
                    min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1);
                }
            }
            cut[i] = min;
        }
        return cut[n - 1];
    }
}