`
standalone
  • 浏览: 619269 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

[leetcode] Palindrome Partition

 
阅读更多
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解决方案

    LeetCode Palindrome Number解决方案 在本节中,我们将讨论如何确定一个整数是否是一个回文数。一个整数是一个回文数当它从左到右读取和从右到左读取相同。 问题描述: 给定一个整数,判断它是否是一个回文数。 ...

    LeetCode9 Palindrome Number

    《LeetCode9:判断回文数——Java实现详解》 在编程的世界里,LeetCode是一个广受欢迎的在线平台,它提供了各种算法问题供程序员们挑战和提升技能。今天我们要探讨的是LeetCode第9题——“回文数”。这道题目要求...

    c语言-leetcode 0009-palindrome-number.zip

    c c语言_leetcode 0009_palindrome_number.zip

    java-leetcode题解之Partition Labels.java

    在《Java-leetCode题解之Partition Labels.java》的文件内容中,可能包含以下知识点: 1. 字符串处理:在处理字符串时,需要掌握如何遍历、查找、比较和修改字符串中的字符。 2. 数据结构应用:理解并应用合适的...

    java-leetcode题解之Palindrome Permutation II.java

    在编程领域中,LeetCode是一个广受欢迎的在线平台,它提供了一系列的编程题目,旨在帮助程序员通过解决实际问题来提高编程技能。特别是对于算法和数据结构的掌握,LeetCode上的题目覆盖了从初级到高级的多个层次。而...

    js-leetcode题解之131-palindrome-partitioning.js

    在JavaScript中,处理leetcode上的编程题目时,正确理解和解决"131.Palindrome Partitioning"这类字符串划分问题是一项重要的技能。... const palindromePartition = (str, temp) =&gt; { if (str.length

    java-leetcode题解之009-Palindrome-Number

    java入门 java_leetcode题解之009_Palindrome_Number

    python-leetcode题解之086-Partition-List

    python python_leetcode题解之086_Partition_List

    java-leetcode题解之Longest Chunked Palindrome Decomposition.java

    在LeetCode上,有一道题目叫做“Longest Chunked Palindrome Decomposition”,也就是“最长块状回文分解”。这个问题主要考察的是算法和编程能力,需要解决者了解回文(palindrome)这个概念。回文是指一个字符串...

    js-leetcode题解之9-palindrome-number.js

    在探讨js-leetcode题解之9-palindrome-number.js的过程中,我们需要先明确几个关键概念。首先,所谓的“palindrome-number”翻译成中文即为“回文数”,这是一种正读和反读都相同的数字。在编程算法中,判断一个数...

    c语言-leetcode题解之0416-partition-equal-subset-sum

    c c语言_leetcode题解之0416_partition_equal_subset_sum

    c语言-leetcode题解之0086-partition-list.zip

    在这些题目中,“LeetCode题解之0086-partition-list”是一个涉及数据结构操作的典型问题,需要利用C语言解决。具体来讲,这个问题要求我们对一个链表进行分区操作。分区操作的基本思想是:给定一个链表和一个特定值...

    python-leetcode题解之132-Palindrome-Partitioning-II

    在众多的LeetCode题库中,“Palindrome Partitioning II” 是一个有趣的字符串处理问题,属于动态规划和字符串分割的范畴。这个问题要求我们编写一个函数,接受一个字符串s作为输入,然后找到使字符串s的子串都是...

    C++-leetcode题解之763. Partition Labels.cpp

    在C++编程语言中,LeetCode是一个广受欢迎的在线...LeetCode 763题“Partition Labels”的C++题解,是对字符串操作和贪心算法理解的一次实践。通过这类题目的解决,不仅可以锻炼编程能力,还能加深对算法思想的认识。

    java-leetcode题解之Can Make Palindrome from Substring.java

    在深入探讨Java实现的LeetCode题解Can Make Palindrome from Substring的详细知识点之前,让我们先了解该题目的背景和要求。该题目要求编写一个Java方法,这个方法需要判断给定字符串的任何子串是否可以通过重新排列...

    python-leetcode题解之234-Palindrome-Linked-List.py

    LeetCode 234 题题解涉及到的是一个链表问题,题目要求判断一个单链表是否为回文结构。回文即正读和反读都一样,对于链表来说,需要考虑到其单向性的特点。针对这个问题,可以使用双指针技巧来解决,一个指针步长为1...

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...

    vscode安装leetcode-palindromeC-:回文C-

    vscode安装leetcode 回文 这是分支、循环和其他基本 C# 概念的练习,以构建工作控制台应用程序。5/5/2020 由 Nitun Dtta 和 Matt Stroud 制作 描述 这是一个控制台应用程序,允许用户提供任何单词、短语、数字或其他...

    LeetCode 101 - A LeetCode Grinding Guide (C Version).pdf

    《LeetCode 101 - A LeetCode Grinding Guide (C++ Version)》是一本面向有一定C++编程基础,但缺乏刷题经验读者的教科书和工具书。作者高畅(Chang Gao)基于其在准备实习和秋招过程中对LeetCode题目的整理和刷题...

    LeetCode 101 - A LeetCode Grinding Guide (C++ Version).rar

    《LeetCode 101 - A LeetCode Grinding Guide (C++ Version)》是一本专为C++程序员设计的深入解析LeetCode算法问题的指南。这本书采用彩色版,以直观的方式讲解了各种数据结构和算法,旨在帮助读者磨练编程技能,...

Global site tag (gtag.js) - Google Analytics