分割回文串

/*
 * 思路：
 * 1. 使用Java Stream的方式实现回溯算法。
 * 2. 通过过滤和映射操作来处理每一个可能的回文子串分割。
 */
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public class PalindromePartitioningStream {
    public List<List<String>> partition(String s) {
        return backtrack(s, 0, new ArrayList<>()).collect(Collectors.toList());
    }
 
    private IntStream backtrack(String s, int start, List<String> currentList) {
        if (start == s.length()) {
            List<List<String>> result = new ArrayList<>();
            result.add(new ArrayList<>(currentList));
            return result.stream();
        }
        return IntStream.range(start, s.length()).filter(end -> isPalindrome(s, start, end)).mapToObj(end -> {
            currentList.add(s.substring(start, end + 1));
            List<List<String>> subResult = backtrack(s, end + 1, currentList).collect(Collectors.toList());
            currentList.remove(currentList.size() - 1);
            return subResult;
        }).flatMap(List::stream);
    }
 
    private boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
}