LeetCode – Palindrome Partitioning II

The first thing that comes up is that we should be able to solve this problem using DFS. For each recursion we do:

1.From designated start point, we scan from len – 1 down to start point to see if s.substring(i, j) is palindrome.
2.If so, we do dfs(s, j + 1), record the minimum cut to end.
3.Ending condition: if start == len, return 0;
4.Return value: minimum cuts + 1
5.In main block, return dfs – 1;

Here there are a couple of things could be optimized:

1.For palindrome verification, we can use dynamic programming to record previous result. This could save a lot of computation. Formula as follows:

If s.charAt(i) == s.charAt(j) && (i == j || j – 1 == i || F(i + 1, j – 1) == true)
THEN F(i, j) (means s.substring(i, j) is palindrome).

2.Use map in step 1 to save operations cutting S as well as palindrome validation.

3.After doing above, we have changed the question to: What is the minimum cuts do we need to reach the end given the steps we could take(map). That means: we could use dynamic programming again to produce this result:

f(i – k, i)(inclusive)  AND s(i) = s(i – k – 1) + 1 means:
If s.substring(i – k, i + 1) is palindrome, to partition s.substring(0, i + 1) the minimum steps will be s(i – k – 1) + 1. (min cuts for s.substring(0, i – k))

Return last record as result.

**NOTE:
Be careful on the differences between inclusive and exclusive indexes.

public class Solution {
    public int minCut(String s) {
        if (s == null || s.length() < 2)
            return 0;
            
        int len = s.length();
        boolean[][] map = new boolean[len][len];
        for (int j = 0; j < len; j++) { for (int i = j; i >= 0; i--) {
                if ((s.charAt(i) == s.charAt(j)) &&
                        (i == j || i == j - 1 || map[i + 1][j - 1]))
                    map[i][j] = true;
            }
        }
        
        int[] splits = new int[len];
        //j represents string index, inclusive
        for (int j = 0; j < len; j++) {    
            splits[j] = Integer.MAX_VALUE;
            //i represents string index, inclusive
            for (int i = 0; i <= j; i++) { if (map[i][j]) splits[j] = Math.min(splits[j], (i > 0? splits[i - 1] + 1 : 1));
            }
        }
        return splits[len - 1] - 1;
    }
}