Palindrome Partitioning, Palindrome Partitioning II, Word Break, Word Break, Word Break II

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = “aab”,
Return

[
  ["aa","b"],
  ["a","a","b"]
]

Solution

• template dfs, for each string try to cut from 0 to s.length

public static List<List<String>> partition(String s) {
    	List<List<String>> res = new ArrayList<List<String>>(); 
    	List<String> tmp = new ArrayList<String>();
    	dfs(res, s, tmp);
    	return res;
    }
    
    private static void dfs(List<List<String>> res, String s, List<String> tmp){
    	if(s.length()==0){
    		res.add(new ArrayList<String>(tmp));
    		return;
    	}
    	for(int i=0; i<s.length(); i++){
    		if(isPalin(s.substring(0, i+1))){
    			tmp.add(s.substring(0, i+1));
    			dfs(res, s.substring(i+1), tmp);
    			tmp.remove(tmp.size()-1);
    		}
    	}
    }
    
    private static boolean isPalin(String s){
    	for(int i=0; i<s.length()/2; i++){
    		if(s.charAt(i) != s.charAt(s.length()-1-i)) return false;
    	}
    	return true;
    }

---

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.
For example, given s = “aab”,
Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

DP Solution O(n^2)

• dp[i] records the minimun cuts for substr[0,i]
• isP[i][j] records if [i,j] is palindrome
• for each char, set to be one cut per char first, then check if contains previous palindrome substrs(including itself as a palindrome)

public int minCut(String s) {
       int n = s.length();
       int[] dp = new int[n];
       boolean[][] isP = new boolean[n][n];
       for(int i=0; i<n; i++){
           dp[i]=i;
           for(int j=i; j>=0; j--){
               if(s.charAt(i)==s.charAt(j) && ((i-j)<2 || isP[j+1][i-1])){//[i,j]is palindrom, s.i must equal s.j
                   isP[j][i]=true;
                   if(j==0){//if is palindrome from start of s
                       dp[i]=0;
                   }
                   else{//else take cut before j
                       dp[i]=Math.min(dp[j-1]+1, dp[i]);
                   }
               }
           }
       }
       return dp[n-1];
   }

---

Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = “leetcode”,
dict = [“leet”, “code”].
Return true because “leetcode” can be segmented as “leet code”.

1D DP Solution

• for each i, take substring [j<=i,i] and check if in set. If yes, and j==0(first match), or dp[j-1]=true(previous string is valid), we can set dp[i] to true

public boolean wordBreak(String s, Set<String> wordDict) {
    boolean[] dp=new boolean[s.length()];
    for(int i=0;i<s.length();i++){
        for(int j=0;j<=i;j++){
            String tmp = s.substring(j,i+1);
            if(wordDict.contains(tmp) && (j==0 || dp[j-1])){
                dp[i]=true;
            }
        }
    }
    return dp[s.length()-1];
}

---

Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = “catsanddog”,
dict = [“cat”, “cats”, “and”, “sand”, “dog”].
A solution is [“cats and dog”, “cat sand dog”].

DP Check + DFS Output Solution

public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> res = new ArrayList<String>();
        boolean[] cancut = new boolean[s.length()];
        for(int i=0;i<s.length();i++){
	        if(wordDict.contains(s.substring(0,i+1))){
	            cancut[i]=true;
	            continue;
	        }
	        for(int j=0;j<=i;j++){
	            if(wordDict.contains(s.substring(j, i+1)) && cancut[j-1]){
	                cancut[i]=true;
	            }
	        }
	    }
	    if(!cancut[s.length()-1]) return res;
	    
        dfs(wordDict, res, new ArrayList<String>(), s, 0);
        return res;
    }
    
	    private static void dfs(Set<String> dict, List<String> res, List<String> tmp, String s, int start){
	        for(int i=start; i<s.length(); i++){
	            String cur = s.substring(start, i+1);
	            if(dict.contains(cur)){
	                tmp.add(cur);
	                if(i==(s.length()-1)){
	                    String each="";
	                    for(String word : tmp){
	                    	each= each +" " +word;
	                    }
	                    res.add(each.trim());
	                    
	                }
	                else{
	                    dfs(dict, res, tmp, s, i+1);
	                }
	                tmp.remove(tmp.size()-1);
	            }
	        }
	    }