一文详解回溯算法如何解决分割回文串 | Java 刷题打卡

简介: 一文详解回溯算法如何解决分割回文串 | Java 刷题打卡

题目描述



这是 LeetCode 上的 131. 分割回文串 ,难度为 中等


Tag : 「回文串」、「回溯算法」、「动态规划」


给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。


回文串 是正着读和反着读都一样的字符串。


示例 1:


输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
复制代码


示例 2:


输入:s = "a"
输出:[["a"]]
复制代码


提示:


  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成


动态规划 + 回溯算法



求所有的分割方案,凡是求所有方案的题基本上都没有什么优化方案,就是「爆搜」。


问题在于,爆搜什么?显然我们可以爆搜每个回文串的起点。如果有连续的一段是回文串,我们再对剩下连续的一段继续爆搜。


为什么能够直接接着剩下一段继续爆搜?


因为任意的子串最终必然能够分割成若干的回文串(最坏的情况下,每个回文串都是一个字母)。


所以我们每次往下爆搜时,只需要保证自身连续一段是回文串即可。


举个🌰 来感受下我们的爆搜过程,假设有样例 abababa,刚开始我们从起点第一个 a 进行爆搜:


  1. 发现 a 是回文串,先将 a 分割出来,再对剩下的 bababa 进行爆搜
  2. 发现 aba 是回文串,先将 aba 分割出来,再对剩下的 baba 进行爆搜
  3. 发现 ababa 是回文串,先将 ababa 分割出来,再对剩下的 ba 进行爆搜
  4. 发现 abababa 是回文串,先将 abababa 分割出来,再对剩下的 `` 进行爆搜

...


然后再对下一个起点(下个字符) b 进行爆搜?


不需要。


因为单个字符本身构成了回文串,所以以 b 为起点,b 之前构成回文串的方案,必然覆盖在我们以第一个字符为起点所展开的爆搜方案内(在这里就是对应了上述的第一步所展开的爆搜方案中)。


因此我们只需要以首个字符为起点,枚举以其开头所有的回文串方案,加入集合,然后对剩下的字符串部分继续爆搜。就能做到以任意字符作为回文串起点进行分割的效果了。


一定要好好理解上面那句话 ~


剩下的问题是,我们如何快速判断连续一段 [i, j] 是否为回文串,因为爆搜的过程每个位置都可以作为分割点,复杂度为 O(2n)O(2^n)O(2n) 的。


因此我们不可能每次都使用双指针去线性扫描一遍 [i, j] 判断是否回文。


一个直观的做法是,我们先预处理除所有的 f[i][j]f[i][j] 代表 [i, j] 这一段是否为回文串。


预处理 f[i][j] 的过程可以用递推去做。


要想 f[i][j] == true ,必须满足以下两个条件:


  1. f[i + 1][j - 1] == true
  2. s[i] == s[j]


由于状态 f[i][j] 依赖于状态 f[i + 1][j - 1],因此需要我们左端点 i从大到小进行遍历;而右端点 j从小到大进行遍历。


因此,我们的遍历过程可以整理为:右端点 j 一直往右移动(从小到大),在 j 固定情况下,左端点 ij 在左边开始,一直往左移动(从大到小)


代码:


class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        // f[i][j] 代表 [i, j] 这一段是否为回文串
        boolean[][] f = new boolean[n][n];
        for (int j = 0; j < n; j++) {
            for (int i = j; i >= 0; i--) {
                // 当 [i, j] 只有一个字符时,必然是回文串
                if (i == j) {
                    f[i][j] = true;
                } else {
                    // 当 [i, j] 长度为 2 时,满足 cs[i] == cs[j] 即回文串
                    if (j - i + 1 == 2) {
                        f[i][j] = cs[i] == cs[j];
                    // 当 [i, j] 长度大于 2 时,满足 (cs[i] == cs[j] && f[i + 1][j - 1]) 即回文串
                    } else {
                        f[i][j] = cs[i] == cs[j] && f[i + 1][j - 1];
                    }
                }
            }
        }
        List<List<String>> ans = new ArrayList<>();
        List<String> cur = new ArrayList<>();
        dfs(s, 0, ans, cur, f);
        return ans;
    }
    /**
     * s: 要搜索的字符串
     * u: 以 s 中的那一位作为回文串分割起点
     * ans: 最终结果集
     * cur: 当前结果集
     * f: 快速判断 [i,j] 是否为回文串
     */
    void dfs(String s, int u, List<List<String>> ans, List<String> cur, boolean[][] f) {
        int n = s.length();
        if (u == n) ans.add(new ArrayList<>(cur));
        for (int i = u; i < n; i++) {
            if (f[u][i]) {
                cur.add(s.substring(u, i + 1));
                dfs(s, i + 1, ans, cur, f);
                cur.remove(cur.size() - 1);
            }
        }
    }
}
复制代码


  • 时间复杂度:动态规划预处理的复杂度为 O(n2)O(n^2)O(n2);爆搜过程中每个字符都可以作为分割点,并且有分割与不分割两种选择,方案数量为 2n−12^{n - 1}2n1,每个字符都需要往后检查剩余字符的分割情况,复杂度为 O(n)O(n)O(n)。整体复杂度为 O(n∗2n)O(n * 2^n)O(n2n)
  • 空间复杂度:动态规划部分的复杂度为 O(n2)O(n^2)O(n2);方案数量最多为 2n−12^{n - 1}2n1,每个方案都是完整字符串 s 的分割,复杂度为 O(n)O(n)O(n),整体复杂度为 O(n∗2n)O(n * 2^n)O(n2n)


总结



对于此类要枚举所有方案的题目,我们都应该先想到「回溯算法」。


「回溯算法」从算法定义上来说,不一定要用 DFS 实现,但通常结合 DFS 来做,难度是最低的。


「回溯算法」根据当前决策有多少种选择,对应了两套模板。


每一次独立的决策只对应 选择 和 不选 两种情况:


  1. 确定结束回溯过程的 base case
  2. 遍历每个位置,对每个位置进行决策(做选择 -> 递归 -> 撤销选择)


void dfs(当前位置, 路径(当前结果), 结果集) {
    if (当前位置 == 结束位置) {
        结果集.add(路径);
        return;
    }
    选择当前位置;    
    dfs(下一位置, 路径(当前结果), 结果集);
    撤销选择当前位置;
    dfs(下一位置, 路径(当前结果), 结果集);
}
复制代码


每一次独立的决策都对应了多种选择(通常对应了每次决策能选择什么,或者每次决策能选择多少个 ...):


  1. 确定结束回溯过程的 base case
  2. 遍历所有的「选择」
  3. 对选择进行决策 (做选择 -> 递归 -> 撤销选择)


void dfs(选择列表, 路径(当前结果), 结果集) {
    if (满足结束条件) {
        结果集.add(路径);
        return;
    }
    for (选择 in 选择列表) {
        做选择;
        dfs(路径’, 选择列表, 结果集);
        撤销选择;
    }
}
复制代码


拓展



刚好最近在更新「回溯算法」的相关题解,以下题目可以加深你对「回溯」算法的理解和模板的运用:


17. 电话号码的字母组合(中等) : 从一道「回溯算法」经典题与你分享回溯算法的基本套路


39. 组合总和(中等) : DFS + 回溯算法,以及如何确定一道题是否应该使用 DFS + 回溯来求解


40. 组合总和 II(中等) : 【回溯算法】求目标和的组合方案(升级篇)


216. 组合总和 III(中等) : 【回溯算法】借助最后一道「组合总和」问题来总结一下回溯算法


37. 解数独(困难) : 【数独问题】经典面试题:解数独


最后



这是我们「刷穿 LeetCode」系列文章的第 No.131 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
12天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
46 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
14天前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
50 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
18天前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
45 2
|
13天前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
8 0
|
14天前
|
算法 Java Linux
java制作海报一:java使用Graphics2D 在图片上写字,文字换行算法详解
这篇文章介绍了如何在Java中使用Graphics2D在图片上绘制文字,并实现自动换行的功能。
40 0
|
15天前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
14 0
|
16天前
|
算法
第七章 回溯算法理论基础
第七章 回溯算法理论基础
12 0
|
22天前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
14 0
|
2月前
|
算法 前端开发
一文了解贪心算法和回溯算法在前端中的应用
该文章深入讲解了贪心算法与回溯算法的原理及其在前端开发中的具体应用,并通过分析LeetCode题目来展示这两种算法的解题思路与实现方法。
|
3月前
|
设计模式 缓存 算法
揭秘策略模式:如何用Java设计模式轻松切换算法?
【8月更文挑战第30天】设计模式是解决软件开发中特定问题的可重用方案。其中,策略模式是一种常用的行为型模式,允许在运行时选择算法行为。它通过定义一系列可互换的算法来封装具体的实现,使算法的变化与客户端分离。例如,在电商系统中,可以通过定义 `DiscountStrategy` 接口和多种折扣策略类(如 `FidelityDiscount`、`BulkDiscount` 和 `NoDiscount`),在运行时动态切换不同的折扣逻辑。这样,`ShoppingCart` 类无需关心具体折扣计算细节,只需设置不同的策略即可实现灵活的价格计算,符合开闭原则并提高代码的可维护性和扩展性。
58 2