LeetCode131(2021.3.7)

LC131. 分割回文串

class Solution {
    public boolean check(List<String> v) {
        for (String s : v) {
            for (int i = 0; i < s.length() / 2; ++i) {
                if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                    return false;
                }
            }
        }
        return true;
    }

    public List<List<String>> partition(String s) {
        int n = s.length();
        List<List<String>> res = new ArrayList<List<String>>();
        List<String> lst = new ArrayList<String>();
        for (int i = 0; i < (1 << (n - 1)); ++i) {
            lst.clear();
            lst.add(String.valueOf(s.charAt(0)));
            for (int j = 0; j < n - 1; ++j) {
                if ((i & (1 << j)) == 0) {
                    lst.set(lst.size() - 1, lst.get(lst.size() - 1) + s.charAt(j + 1));
                }
                else {
                    lst.add(String.valueOf(s.charAt(j + 1)));
                }
            }
            if (check(lst)) {
                res.add(new ArrayList<String>(lst));
            }
        }
        return res;
    }
}