http://leetcode.com/onlinejudge#question_131
Question:
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"]
]
Solution:
This is also a DP. I like DP
import java.util.ArrayList;
public class Partition {
public ArrayList<ArrayList<String>> partition(String s) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
int length = s.length();
if(length ==1){
ArrayList<String> a = new ArrayList<String>();
a.add(s);
result.add(a);
return result;
}
for(int i=0; i< length; i++){
String str = s.substring(0, i+1);
if(isP(str)){
if(i+1 == length){
ArrayList<String> a = new ArrayList<String>();
a.add(str);
result.add(a);
}else {
ArrayList<ArrayList<String>> temp = partition(s.substring(i+1));
for(ArrayList<String> a : temp){
a.add(0, str);
result.add(a);
}
}
}
}
return result;
}
public boolean isP(String s){
int length = s.length();
if(length == 1 || length ==0) return true;
int i=0; int j= length-1;
while(s.charAt(i) == s.charAt(j) && i<j){
i++;j--;
}
if(i<j) return false;
else return true;
}
public static void printResult (ArrayList<ArrayList<String>> array){
for(ArrayList<String> a: array){
for(String s: a){
System.out.print("\t" + s);
}
System.out.println();
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "ddfdsfadf";
Partition p = new Partition();
Partition.printResult(p.partition(str));
}
}
分享到:
相关推荐
LeetCode Palindrome Number解决方案
Determine whether an integer is a palindrome. Do this without extra space. Java AC版本
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
vscode安装leetcode 回文 这是分支、循环和其他基本 C# 概念的练习,以构建工作控制台应用程序。5/5/2020 由 Nitun Dtta 和 Matt Stroud 制作 描述 这是一个控制台应用程序,允许用户提供任何单词、短语、数字或其他...
Leetcode\PalindromeNumber\PalindromeNumber.cs 问题: 从排序数组中删除重复项 代码: Leetcode\RemoveDuplicates\RemoveDuplicates.cs 问题: 买卖股票的最佳时机 II 代码: Leetcode\MaxProfit\MaxProfit.cs ...
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
vs code LeetCode 插件
leetcode中文版
Palindrome LeetCode 167 Two Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels of a String 2 字符串 编号 题目 LeetCode 3 Longest Substring Without Repeating ...
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
方法1 思路:将链表中的元素都保存list中,并判断这个list和反转后的list,是否相同,如果相同,则回文;否则,则不回文。 性能分析:时间复杂度为O(n);空间复杂度为O(n) [因为用到了extra space list] ...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...