题目地址(131. 分割回文串)

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

题目描述

  1. 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
  3. 回文串 是正着读和反着读都一样的字符串。
  7. 示例 1：
  9. 输入：s = "aab"
  10. 输出：[["a","a","b"],["aa","b"]]
  13. 示例 2：
  15. 输入：s = "a"
  16. 输出：[["a"]]
  21. 提示：
  23. 1 <= s.length <= 16
  24. s 仅由小写英文字母组成

前置知识


公司

  • 暂无

思路

本题这涉及到两个关键问题：

  1. 切割问题，有不同的切割方式
  2. 判断回文

其实切割问题类似组合问题。
例如对于字符串abcdef：

  • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…..。
  • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…..。

image.png
判断回文子串
最后我们看一下回文子串要如何判断了，判断一个字符串是否是回文。

可以使用双指针法，一个指针从前向后，一个指针从后先前，如果前后指针所指向的元素是相等的，就是回文字符串了。

关键点

  • 怎么判断是不是回文串
    • 双指针对向遍历
  • 递归如何终止
    • 起始位置大于s的大小

代码

  • 语言支持：Java

Java Code:

  2. class Solution {
  3.         ArrayList<List<String>> res = new ArrayList<>();
  4.         ArrayList<String> path = new ArrayList<>();
  5. //        Deque<String> path = new LinkedList<>();
  6.         public List<List<String>> partition(String s) {
  7.             loop(s,0);
  8.             return res;
  9.         }
  10.         void loop(String s , int startIndex){
  11.             //终止条件 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
  12.             if (startIndex >= s.length()) {
  13.                 res.add(new ArrayList<>(path));
  14.                 return;
  15.             }
  16.             //从0开始 循环数组长度次
  17.             for (int i = startIndex; i < s.length() ; i++) {
  18.                 //判断是不是回文数 如果是 就把当前的与层数对应的字符串截取 然后添加到路径
  19.                 //如果不是 就跳过当次循环 第一次碰到就是把单个字符判断成回文串 递归回来在判断后面的
  20.                 if (judge(s, startIndex, i)) {
  21.                     path.add(s.substring(startIndex, i+1));
  22.                 }else {
  23.                     continue;
  24.                 }
  25.                 //递归 下一层由i+1来作为startIndex
  26.                 loop(s,i+1);
  27.                 //回溯 递归后返回将最后一个数删了
  28.                 path.remove(path.size()-1);
  29.             }
  30.         }
  31.         //使用双指针 从前后分别遍历 如果遇到不相等的情况就返回false 其他都为true
  32.         boolean judge(String s,int start , int end){
  33.             for (int i = start , j = end ; i < j ; i++ , j--) {
  34.                 if (s.charAt(i) != s.charAt(j)) {
  35.                     return false;
  36.                 }
  37.             }
  38.             return true;
  39.         }
  40.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：131. 分割回文串 - 图2#card=math&code=O%28n%29&id=ffdK2)
  • 空间复杂度：131. 分割回文串 - 图3#card=math&code=O%28n%29&id=u5hWn)