[LeetCode] 131. Palindrome Partitioning

轉自LeetCode

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>
這題原本想用 DP 的方式來解

但因為答案需要所有的字串組合，所以最後還是使用 DFS 來找所有的組合

想法如下

• 檢查當下的 partition 是否可以形成一個 palindrome，如果可以，就先放到 vector裡面

• 使用 DFS 的概念，繼續往下找，當已經處理到最後一個字元，就放到 ans 裡面

code 如下(參考資料)

	class Solution {
	vector<vector<string>> ans;
	vector<string> out;
	public:
	vector<vector<string>> partition(string s) {
	//>> use DFS to find all the partition
	DFS(0, s);
	return ans;
	}
	void DFS(const int &start, const string &s) {
	//>> all parition are done
	if(start == s.length()) {
	ans.push_back(out);
	return;
	}
	//>> DFS
	for(int i = start; i < s.length(); i++) {
	if(isPalindrome(s, start, i)) {
	out.push_back(s.substr(start, i - start + 1));
	DFS(i + 1, s);
	out.pop_back();
	}
	}
	}
	bool isPalindrome(const string &s, int start, int end) {
	while(start <= end) {
	if(s[start] != s[end]) {
	return false;
	}
	++start;
	--end;
	}
	return true;
	}
	};

view raw findAllPalindromePartition_1.cpp hosted with ❤ by GitHub