LeetCode OJ:Palindrome Partitioning II

Palindrome Partitioning II
Total Accepted: 3866
Total Submissions: 22882 My Submissions
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. 제목을 보고 가장 먼저 떠오르는 것은 귀환이다. 비록 가지치기를 했지만 TLE는 통하지 않는다.
4

class Solution{
public:
	int palindrome(string s,int l,int r){
		while(r&&l<s.length()&&s[l]==s[r]){
			l++;r--;
		}
		if(l<r)return 0;
		return r-l-1;
	}
	void dfs(string str,int k,int n,int &minC){
		
		if(k>str.length()-1){
			minC=minC>n?n:minC;
			return;
		}
		if(n>=minC)return;
		for(int i=str.length()-1;i>=k;i--){
			int c=palindrome(str,k,i);
			if(c){
				n++;
				dfs(str,i+1,n,minC);
				n--;
			}
		}
	}
	int minCut(string s){
		int minC=0x7ffffff;
		dfs(s,0,0,minC);
		return minC-1;
	}
};

2. 이런 최소 개수를 구하는 문제를 해결하는 데 동태적인 기획이 가장 효과적인 방식이다.
문자열의 그룹 길이는len이고 dp[i,j]는 i에서 j까지의 최소 분할수이며 dp[i,len]=min{dp[i,j]+dp[j+1,len]}가 있다.우리는 임의의 i, j 간의 최소 분할수를 구할 필요가 없기 때문에 간단하게 볼 때 1차원 그룹을 사용하면 된다. dp[j]가 저장한 것이 j에서len까지의 최소 분할수라면 i<=j현재의 문제는 i에서 j가 회문열인지 아닌지를 판단하는 것이다. 만약에 매번 순환 판단을 이용하면 효율이 너무 낮기 마련이다. 여기도 하나의 동적 계획과 관련된다. flag[i][j]를 설정하면 i에서 j가 회문열인지 아닌지를 저장한다. 만약에 flag[i+1][j-1]이true이고 문자열 s[i]==s[j]를 설정하면 flag[j]=true가 있다. 그렇지 않으면false이다. 여기서 i가 true이고 i와 인접하고 i=j]가 [j]가 [j]]이다.flag[i][j]도 true입니다.

class Solution{
public:
	int minCut(string s){
		int len=s.length();
		vector<int> dp(len+1);
		for(int i=0;i<=len;i++)dp[i]=len-i;
		vector<vector<bool>> flag;
		flag.resize(len+1);
		for(int i=0;i<=len;i++){
			flag[i].assign(len+1,false);
		}
		for(int i=len-1;i>=0;i--){
			for(int j=i;j<len;j++){
				if(s[i]==s[j]&&(j-i<=1||flag[i+1][j-1])){
					flag[i][j]=true;
					dp[i]=min(dp[i],dp[j+1]+1);
				}
			}
		}
		return dp[0]-1;
	}
};

3. 위에서 설정한 dp가 저장한 i에서 문자열 끝까지의 최소 분할수, 현재 반대로 dp[i]는 0에서 i까지의 최소 분할수를 저장하고 조금만 처리하면 된다. 만약에 j에서 i가 회문열이면 dp[i]=min{dp[i], dp[j-1]+1}가 있다.여기에 j-1이 있기 때문에 수조가 경계를 넘지 않도록 1에서len까지 옮길 수 있습니다. 상응하는 dp와flag는 i(1에서len까지) 위치로 문자열보다 1이 더 많이 저장됩니다.

class Solution{
public:
	int minCut(string s){
		int len=s.length();
		vector<int> dp(len+1);
		for(int i=0;i<=len;i++)dp[i]=i;
		vector<vector<bool>> flag;
		flag.resize(len+1);
		for(int i=0;i<=len;i++){
			flag[i].assign(len+1,false);
		}
		for(int i=1;i<=len;i++){
			for(int j=1;j<=i;j++){
				if(s[i-1]==s[j-1]&&(i-j<=1||flag[j+1][i-1])){
					flag[j][i]=true;
					dp[i]=min(dp[i],dp[j-1]+1);
				}
			}
		}
		return dp[len]-1;
	}
};

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)

이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

LeetCode OJ:Palindrome Partitioning II

좋은 웹페이지 즐겨찾기