新博文地址:[leetcode]Palindrome Partitioning
新代码要简洁一点。。。。
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"]
]
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
将字符串分割,每一小段都是回文段,返回所有的分割情况。DFS不解释啊。
算法思想:
首先检查s的前i个字符的子串是不是回文串,如是就递归检查从i+1往后的字串,否则就返回,检查前i+1个字符形成的子串。
对回溯算法用的还不是很熟悉,感觉代码总是略长,但是好在更容易理解。
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>(); public ArrayList<ArrayList<String>> partition(String s) { if(s == null || s.length() == 0){ return result; } for(int i = 0 ; i < s.length(); i++){ ArrayList<String> subList = new ArrayList<String>(); String subStr = s.substring(0, i + 1);//得到前i个字符的子串 if(isPalindrome(subStr)){//如果是回文的,则递归 subList.add(subStr); dfs(s.substring(i + 1), subList); subList.remove(subList.size() - 1);//回溯 } } return result; } private void dfs(String s,ArrayList<String> list){ if(s.length() == 0){ ArrayList<String> cpy = new ArrayList<String>(list); result.add(cpy); return; } for(int i = 0; i < s.length(); i++){ String subStr = s.substring(0, i + 1); if(isPalindrome(subStr)){ list.add(subStr); dfs(s.substring(i + 1),list); list.remove(list.size() - 1); } } } private boolean isPalindrome(String s){ for(int i = 0; i < s.length()>>1; i++){ if(s.charAt(i)!= s.charAt(s.length() - 1 - i)){ return false; } } return true; }
相关推荐
LeetCode Palindrome Number解决方案
Determine whether an integer is a palindrome. Do this without extra space. Java AC版本
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 ...Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
# [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 插件
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 ...
leetcode中文版
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only element which exists once/twice... - count
100个leetCode详细解答
方法1 思路:将链表中的元素都保存list中,并判断这个list和反转后的list,是否相同,如果相同,则回文;否则,则不回文。 性能分析:时间复杂度为O(n);空间复杂度为O(n) [因为用到了extra space list] ...
leetcode刷题, 直接用leetcode的分类方式.
LeetCode 刷题汇总1
LeetCode 选讲1