问题描述
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab"
,
Return
[ ["aa","b"], ["a","a","b"] ]
原问题链接:https://leetcode.com/problems/palindrome-partitioning/
问题分析
这是个关于回文划分的问题 ,问题的要求是得出所有划分的情况。一开始碰到这个问题的时候,有点找不到思路,我们该怎么来考虑这个问题呢?先从一个最基本的情况开始吧。
假定有一个字符串"abcde",对于这个串来说,它里面的每个单独的字符a, b, c都可以认为是一个回文。所以最起码有这么一个每个单独字符组成的划分情况。可是在字符串里面可能会存在一些回文,这些需要判断和划分出来。我们从最基本的情况来考虑,尝试看能否发现一些规律:
假设字符串s本身就是空串,这个时候,我们的划分数为0。对于这种情况可以认为是返回一个空的列表。假设用list来表示它的划分情况,则这里表示为一个空的list,即为[]。
对于长度为1的串来说,它有一个唯一的划分,就是包含这个元素本身。所以它的划分为[i],假设i为该元素。
再进一步来看长度为2的串。假设这个串为"ab",这个时候,因为"ab"本身不是回文,所以它的划分只有["a", "b"]这种情况。如果这个串本身为回文呢?比如说这个串为"aa",这个时候,除了前面单个元素的["a", "a"],还要划分["aa"]。进一步细化的分析来看,对于长度为2的串,假定p[i]表示从0开始到元素i的所有划分。那么它所有的划分则如下,我们首先看长度为0的情况,当0到i的串构成一个回文,则对应长度0和这个回文串构成一个划分,比如这里的"aa"。在长度为1的情况,对应第一个元素的所有划分情况为["a"],而后面的这个元素是单独的一个元素,也是一个回文,所以它们构成划分["a", "b"]或者["a", "a"]。这样,我们可以概括出一个这样的规律,
p[i] = p(k) + substring(k, i),if(substring(k, i)) 是回文。k = 0, 1, ... i
按照这个递归的关系,我们尝试递推一下划分的数量,比如有如下图的字符串:
假定p[i]表示对应前面i个元素,则有如下的情况:
p[0] = [] 这个时候没有选择任何元素,所以为空。
p[1] = ["a"],仅有一个元素,选择"a"。
p[2] = ["a", "b"],我们首先看0到2,这个时候的两个元素为ab,它们不是回文,所以应该跳过。然后再看1到2,因为是单独的a和b,所以有p[2] = p[1] + "b"。如下图:
p[3] = ["aba"] ["a", "b", "a"],还是老样子从0开始看,从0到3的串为aba,它本身为回文,所以应该加入到里面。后面的1和2到3都不构成回文,所以跳过。
p4= ["a", "bab"] ["aba", "b"] ["a", "b", "a", "b"]它分别对应着p[1] + "bab", p[3] + "b"。这里p[3] + "b"对应有两种情况,就是前面的["aba", "b"]和["a", "b", "a"]。
所以,前面说了这么多,这个递推的关系就是每次对元素前面的部分进行遍历,如果前面遍历的某个点和当前点构成回文,则将这个回文部分和前面的对应点部分拼起来,这样就构成了一个划分。用伪代码描述的话,则如下:
for(int j = 0; j <= i; j++) { if([i, j]为回文) { for(list l : lists[j]) { newl = clone(l) // 做一份原来list的copy newl.add(s[j, i]); //将j到i的这部分字符串加入到新串中。 list[i].add(newl); //这时候newl对应着一个划分,将它加入到i所在的划分集合中。 } } }
这部分代码对应的是在长度为i的情况下,我们设定这个位置对应的划分列表。仔细看这部分代码的话,还要一个问题就是我们需要考虑的。因为这里有一个判断就是[i, j]这一段字符串是否为回文。所以,有了前面的基础之后,我们需要仔细考虑一下怎么判断它们。如果我们只是每次拿到一个序列的开头就这么去遍历的判断,这样虽然可行,但是很多时候是重复执行了很多运算的。所以这部分也需要仔细考虑一下。
回文判断和改进
如果单纯从对一个字符串是否为回文的角度来判断的话,我们可以很简单的通过一个for循环从两头往中间比较来实现。在这个问题的场景中,我们需要比对对应位置i来说,从0开头到i之间所有子串。如果每次都这么循环的比对,似乎效率比较低。那么,能否通过一种方式将结果记录下来方便后面直接查找呢?
对于字符串来说,假设它的长度为n,那么对应的可能有n * n种。所以,我们可以考虑用一个n * n的矩阵来记录。对于里面所有i == j的情况,相当于对应这个i元素本身。所以如果用一个矩阵p[][]来表示这些判断的话,那么p[i][i] == true。
再延伸一下,如果i,j 之间相差一个呢?这就是说这两个元素是相邻的,要判断它们是否为回文,只要保证s[i] == s[j]就可以了。所以对于相邻的元素p[i-1][i] = p[i-1] == p[i]。
如果我们再概括到一个更一般的情况呢?如下图,我们考察字符串s[i, j]:
对于这个串来说,如果开头结尾的s[i]和s[j]不相等的话,它肯定就不是一个回文了。如果它们相等呢?这个时候就取决于里面的s[i+1, j-1]这个子串了。如果里面这个是,s[i, j]就是。所以,通过这一系列的讨论,我们又得到一个如下的递推关系:
假设j >= i。
1. i == j时,p[i][j] = true
2. j == i + 1时,p[i][j] = s[i] == s[j],取决于相邻两个元素是否相等。
3. 其他,p[i][j] = (s[i] == s[j]) && p[i+1][j-1]。针对递归的情况,取决于当前两个元素是否相等且内部的子串是否也是回文。
经过这一番讨论,我们就得到了一个判断回文的递归表达式。将回文判断结果保存到一个矩阵里的方法实现如下:
void checkPalindrome(String s) { int n = s.length(); boolean[][] p = new boolean[n][n]; for(int j = 0; j < n; j++) { for(int i = 0; i <= j; i++) { if(i == j) p[i][j] = true; else if(j - i == 1) p[i][j] = s.charAt(i) == s.charAt(j); else p[i][j] = p[i+1][j-1] && (s.charAt(i) == s.charAt(j)); } } }
实现和改进
有了前面判断某两个节点之间是否构成回文的基础,我们再把前面划分的部分详细做一个实现:
public class Solution { boolean[][] pair; public List<List<String>> partition(String s) { checkPalindrome(s); int len = s.length(); List<List<String>>[] result = new List[len + 1]; result[0] = new ArrayList<List<String>>(); result[0].add(new ArrayList<String>()); for(int i = 0; i < s.length(); i++){ result[i + 1] = new ArrayList<List<String>>(); for(int j = 0; j <= i; j++){ if(pair[j][i]){ String str = s.substring(j, i + 1); for(List<String> r : result[j]){ List<String> ri = new ArrayList<String>(r); ri.add(str); result[i + 1].add(ri); } } } } return result[len]; } }因为我们前面需要利用checkPalindrome方法生成的boolean[][]矩阵,所以将这个矩阵定义成类的成员变量。这里的实现有几个要注意的细节点。
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
Determine whether an integer is a palindrome. Do this without extra space. Java AC版本
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
Leetcode\PalindromeNumber\PalindromeNumber.cs 问题: 从排序数组中删除重复项 代码: Leetcode\RemoveDuplicates\RemoveDuplicates.cs 问题: 买卖股票的最佳时机 II 代码: Leetcode\MaxProfit\MaxProfit.cs ...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
leetcode:leetcode刷题
加油站问题leetcode LeetCode LeetCode-JS分类列表: :smiling_face_with_smiling_eyes: :flushed_face: :winking_face: :face_with_tongue: :face_with_open_mouth: :beaming_face_with_smiling_...
LeetCode:LeetCode的代码
Leetcode:LeetCode解题代码
LeetCode:LeetCode的注释