LeetCode: Palindrome Partition

题目

https://oj.leetcode.com/problems/palindrome-partitioning/

分析

DFS来解决这个问题。

代码

class Solution
{
public:
	vector<vector<string>> partition(string s)
	{
		if (s.empty())
			return res;

		dfs(s, 0);

		return res;
	}

	void dfs(const string &s, int index)
	{
		if (index == s.size())
			res.push_back(solution);
		else
		{
			for (int i = index; i < s.size(); i++)
			{
				string substr = s.substr(index, i-index+1);
				if (isPalindrome(substr))
				{
					solution.push_back(substr);
					dfs(s, i+1);
					solution.pop_back();
				}
			}
		}
	}
		
	bool isPalindrome(const string &s)
	{
		int left = 0;
		int right = s.size() - 1;

		while (left <= right)
		{
			if (s[left] != s[right])
				return false;
			left++;
			right--;
		}
		return true;
	}

	vector<vector<string>> res;
	vector<string> solution;
};

参考

http://fisherlei.blogspot.com/2013/03/leetcode-palindrome-partitioning.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39064961

/** * RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS. * LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/ /* var disqus_config = function () { this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable }; */ (function() { // DON'T EDIT BELOW THIS LINE var d = document, s = d.createElement('script'); s.src = 'https://chenzz.disqus.com/embed.js'; s.setAttribute('data-timestamp', +new Date()); (d.head || d.body).appendChild(s); })();