Palindrome Partitioning
Total Accepted:4585Total
Submissions:18745My Submissions
Given a strings, partitionssuch that every substring of the partition is a palindrome.
Return all possible palindrome partitioning ofs.
For example, givens="aab"
,
Return
[
["aa","b"],
["a","a","b"]
]
典型的递归回溯法,当然可以利用动态规划法提高点效率。
下面是标准的递归回溯程序:
vector<vector<string> > partition(string s)
{
vector<vector<string> > rs;
vector<string> tmp;
storePatition(rs, tmp, s);
return rs;
}
void storePatition(vector<vector<string> > &rs, vector<string> &tmp,
string &s)
{
if (s.empty())
{
rs.push_back(tmp);
return;
}
for (int i = 1; i <= s.length(); i++)
{
string a = s.substr(0, i);
if (isPalindrome(a))
{
tmp.push_back(a);
string b = s.substr(i);
storePatition(rs, tmp, b);
tmp.pop_back();
}
}
}
bool isPalindrome(string &s)
{
for (int i = 0, j = s.length()-1; i < j; i++, j--)
{
if (s[i] != s[j]) return false;
}
return true;
}
//2014-2-18 update
vector<vector<string> > partition(string s)
{
vector<vector<bool> > table(s.length(), vector<bool>(s.length(), true));
genTable(table, s);
vector<vector<string> > rs;
vector<string> tmp;
part(rs, tmp, table, s);
return rs;
}
void part(vector<vector<string> > &rs, vector<string> &tmp,
vector<vector<bool> > &table, string &s, int start=0)
{
if (start == s.length())
{
rs.push_back(tmp);
return;
}
for (int d = 1; d <= s.length()-start; d++)
{
if (table[start][start+d-1])
{
tmp.push_back(s.substr(start, d));
part(rs, tmp, table, s, start+d);
tmp.pop_back();
}
}
}
void genTable(vector<vector<bool> > &table, string &s)
{
for (int d = 2; d <= s.length(); d++)
{
for (int i = 0, j = d - 1; j < s.length(); i++, j++)
{
table[i][j] = (table[i+1][j-1] && s[i] == s[j]);
}
}
}
分享到:
相关推荐
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