leetcode 제목: Palindrome Partitioning 및 Palindrome Partitioning II

제목 1:
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"]
  ]
문제 풀이 사고방식:
1) 둘 사이의 회문 여부를 2차원 그룹으로 저장한다.
2) 문자열 끝부분부터 가능한 문자열을 저장합니다.
코드:
class Solution {
public:
	vector> partition(string s)
	{
		int len = s.size();
		vector>f(len+1,vector(len));
		for (int i=1;i=0;j--)
			{
				if(ispalindrome(s,j,i-1)==1)
				{
					f[i][j]=true;
				}
			}
		}	
		dealstring(s,len,f);
		return m_str;
	}
private:
	vector>m_str;
	vectorm_temstr;
	void dealstring(string s,int count,const vector>&f)
	{
		if (count == 0)
		{
			vectoroneanswer(m_temstr.rbegin(),m_temstr.rend());
			m_str.push_back(oneanswer);
		}
		for (int i=0;i

제목 2:
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s =  "aab" , Return  1  since the palindrome partitioning  ["aa","b"]  could be produced using 1 cut.
문제 해결 방법:
1) 2차원 그룹 저장으로 둘 사이의 회문 여부를 판단한다.
2) 이 점에서 오른쪽으로 가는 최소 절수를 1차원 그룹으로 동시에 접근한다.
코드:
class Solution {
public:
	int minCut(string s)
	{
	    int size = s.size();
	    int mincount[size+1];
	    vector >m_bool(size,vector(size));
	    for(int i=0;i<=size;i++)
	    {
	        mincount[i] = size-1-i;
	    }
	    for(int j=size-1;j>=0;j--)
	    {
	        for(int k = j;k

좋은 웹페이지 즐겨찾기