leetcode-palindrome-partitioning

题目大意

　　https://leetcode.com/problems/palindrome-partitioning/

　　对一个字符串做划分，要求划分后的每个子串都是回文串，例如"aab"，输出：

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

题目分析

　　深度优先搜索，注意check方法检查一个字符串是否是回文，利用记忆化做了优化。

代码

public class Solution {
    private char[] c;
    private int len;
    private List<List<String>> ans;
    private char[][] f;
    private String[] path;
    private String s;
    
    private boolean check(int si, int ei) { // [s,e]
        if (si == ei) {
            return true;
        }
        if (si + 1 == ei) {
            return c[si] == c[si + 1];
        }
        if (f[si][ei] > 0) {
            return f[si][ei] == 1;
        }
        if (c[si] == c[ei]) {
            boolean v = check(si + 1, ei - 1);
            if (v) {
                f[si][ei] = 1;
            } else {
                f[si][ei] = 2;
            }
            return f[si][ei] == 1;
        } else {
            f[si][ei] = 2;
            return false;
        }
    }
    
    private void search(int idx, int step) {
        if (idx > len - 1) {
            List<String> tmp = new ArrayList<String>();
            for (int i = 0; i < step; i++) {
                tmp.add(path[i]);
            }
            ans.add(tmp);
            return;
        }
        for (int i = idx; i < len; i++) {
            if (check(idx, i)) {
                path[step] = s.substring(idx, i + 1);
                search(i + 1, step + 1);
            }
        }
    }
    
    public List<List<String>> partition(String s) {
        c = s.toCharArray();
        len = c.length;
        ans = new ArrayList<List<String>>();
        f = new char[len][len];
        path = new String[len];
        this.s = s;
        search(0, 0);
        return ans;
    }
}