Leetcode每日一题（分割回文串Ⅰ）

分割回文串Ⅰ 

import java.util.ArrayList;
import java.util.List;

class Solution {
    private List<List<String>> ans = new ArrayList<>();
    boolean f[][] = new boolean[1010][1010];//i到j的字符是否为回文串

    public  static void main(String[] args) {
        System.out.println(new Solution().partition("bbab"));
    }
    public void dfs(String s, int u, List<String> path) {//从0到u所有子串
        if (u == s.length()) {//如果一次遍历完成，返回路径
            ans.add(new ArrayList<>(path));
        } else {
            for (int i = u; i < s.length(); i++) {//从当前下标寻找回文串
                if (f[i][u] == true) {//i到u是否为回文串
                    path.add(s.substring(u, i + 1));
                    dfs(s, i + 1, path);
                    path.remove(path.size() - 1);
                }
            }
        }
    }

    public List<List<String>> partition(String s) {
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (i == j) f[i][j] = true;//如果是一个字符时 是回文串
                else if (s.charAt(i) == s.charAt(j)) {//当两个字符相等
                    //1，当前字符串长度为2 2，当前字符串除了首尾的字符的子字符串为回文串
                    if (i == j + 1 || f[i - 1][j + 1] == true) {
                        f[i][j] = true;
                    }
                }
            }
        }
        dfs(s, 0, new ArrayList<>());//从下标为u开始的回文串
        return ans;
    }
}