原题链接:http://oj.leetcode.com/problems/palindrome-partitioning/这道题是求一个字符串中回文子串的切割,并且输出切割结果,其实是Word
Break II和Longest
Palindromic Substring结合,该做的我们都做过了。首先我们根据Longest
Palindromic Substring重大方法建立一个字典,得到字符串中的任意子串是不是回文串的字典,不熟悉的朋友可以先看看哈。接下来就跟Word
Break II一样,根据字典的结果进行切割,然后按照循环处理递归子问题的方法,如果当前的子串满足回文条件,就递归处理字符串剩下的子串。如果到达终点就返回当前结果。算法的复杂度跟Word
Break II一样,取决于结果的数量,最坏情况是指数量级的。代码如下:public ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
if(s==null || s.length()==0)
return res;
helper(s, getDict(s),0,new ArrayList<String>(), res);
return res;
}
private void helper(String s, boolean[][] dict, int start, ArrayList<String> item, ArrayList<ArrayList<String>> res)
{
if(start==s.length())
{
res.add(new ArrayList<String>(item));
return;
}
for(int i=start;i<s.length();i++)
{
if(dict[start][i])
{
item.add(s.substring(start,i+1));
helper(s,dict,i+1,item,res);
item.remove(item.size()-1);
}
}
}
private boolean[][] getDict(String s)
{
boolean[][] dict = new boolean[s.length()][s.length()];
for(int i=s.length()-1;i>=0;i--)
{
for(int j=i;j<s.length();j++)
{
if(s.charAt(i)==s.charAt(j) && ((j-i<2)||dict[i+1][j-1]))
{
dict[i][j] = true;
}
}
}
return dict;
}
同样,这里同Word
Break II一样也可以使用动态规划的方法,但是要对所有中间结果进行存储,花费大量的空间,这里就不列举代码了。这道题扩展还有Palindrome
Partitioning II,虽然求解的问题类似,但是因为一些细节的不同,复杂度会有很大的变化,有兴趣的朋友可以看看哈。
分享到:
相关推荐
Palindrome Sub-Array,Problem Description A palindrome sequence is a sequence which is as same as its reversed order. For example, 1 2 3 2 1 is a palindrome sequence, but 1 2 3 2 2 is not. Given a 2-...
partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only element which exists once/twice... - count
leetcode 分配Leetcode 回文素数禁食解 几个具有 0ms 执行时间的解决方案和 leetcode 问题的基准。 基准测试结果 Benchmark_primePalindrome/letientai299-12 20000 95646 ns/op 1008 B/op 29 allocs/op ...
vscode安装leetcode 回文 这是分支、循环和其他基本 C# 概念的练习,以构建工作控制台应用程序。5/5/2020 由 Nitun Dtta 和 Matt Stroud 制作 描述 这是一个控制台应用程序,允许用户提供任何单词、短语、数字或其他...
gas station leetcode 在牛客网上的在线编程...palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca
C#,回文分割问题(Palindrome Partitioning Problem)算法与源代码 1 回文串 “回文串”是一个正读和反读都一样的字符串,初始化标志flag=true,比如“level”或者“noon”等等就是回文串。 2 回文分割问题 给定...
资源来自pypi官网。 资源全名:check-palindrome-kriti-0.0.1.tar.gz
LeetCode Palindrome Number解决方案
Palindrome Number 先将整数转为字符串:s=str(i) 然后使用 Python inbulit 方法对字符串进行反转:[::-1] 然后将字符串转为整数:i=int(s) 注意 Python 有Int 类型的默认范围:-2147483647 到 2147483647,因此如果...
vscode-leetcode, you can fuck leetcode easily. 还有各位discuss tab下面的大佬们,受益匪浅,希望能多多思考,多用别的角度考虑问题。 Easy 1 - Two Sum 建一个哈希表key是值value是下标直接查,找不到的话就存...
palindrome number in c
leetcode题库 LeetCode-Go 理论基础 见Note 脑图 TODO 待填充 算法题 面试高频出现,以及一些非常经典重要的算法题优先 题目列表 No Title Link Solution Acceptance ...Palindrome Number 49.4% Easy
Palindrome Number 回文数字 10. Regular Expression Matching 动态规划,列出转换方程即可,注意初值 记T[i][j] = 是否S[0:i]和P[0:j]匹配 再分类讨论,其中pattern *分为0, 1, more三种类型 0: i不变, j+1
分割数组求最大差值leetcode ...Palindrome Number 56.7% 简单 10 Regular Expression Matching 25.3% 困难 11 Container With Most Water 59.3% 中等 12 Integer to Roman 61.8% 中等 13 Roman to In
Palindrome Number 回文数 11 Container With Most Water 盛最多水的容器 13 Roman to Integer 罗马数字转整数 14 Longest Common Prefix 最长公共前缀 20 Valid Parentheses 有效的括号 26 Remove Duplicates from ...
Palindrome 是的 2018-10-02 HashTable , Math —— 是的 2018-10-03 String 是的 2018-10-03 GCD , Math , HashTable 不,几乎(想不出好的 GCD 公式) 2018-10-07 LinkedList 是的 2018-10-07 String , ...
leetcode实现strstr leetcode-js 记录刷leetcode分析过程,希望一点点进步! leetcode地址 刷题顺序 按照顺序刷第一遍,记录实现思路,自己的优化方案,并研究高票大佬的...Palindrome Number 双指针 2019/09/17 0010
9-palindrome-number 13 cargo run --bin 13-roman-to-integer 14 cargo run --bin 14-longest-common-prefix 17 cargo run --bin 17-letter-combinations-of-a-phone-number 20 cargo run --bin 20-valid-...
leetcode 分类 ...Palindrome II Easy 数据结构 二叉树 题目 难度 原题 解答 26. 树的子结构 中等 未分类 鸣谢 题目选择、分类参考了 关于 同步自我的博客:, 欢迎关注我的微信公众号「清风迅来」
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 ...Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar