LintCode - 문서 문자열 분할 II
s가 요구에 부합되는 최소 분할 횟수를 되돌려줍니다.
당신은 실제 면접에서 이 문제를 만난 적이 있습니까?
Yes
예제
예를 들어 문자열 s = "aab"을 주고
문자열 s를 [aa','b'] 두 개의 문자열로 분할할 수 있기 때문에 1을 되돌려줍니다
라벨
Expand
관련 문제
Expand
분석: 처음에 n의 dp를 세 번 썼는데 그 결과 시간이 초과되었다. 그 차이는 dp[i][j]=min(dp[i][k]+dp[k+1][j]+1)의 사상이다. 그러면 반드시 그것을 n제곱의 dp로 최적화시켜야 한다. 그래서 워드브레이크 문제를 연상하게 된다. 만약에 s[i][j]가 회문열이면 dp[j]=dp[i-1]+1으로 2차원 dp에서 1차원 dp로 간소화하여 복잡도를 낮출 수 있다.
코드:
class Solution {
public:
/**
* @param s a string
* @return an integer
*/
int minCut(string s) {
// write your code here
int n = s.length();
vector<vector<bool> > dp1(n,vector<bool>(n,false));
for(int len = 1;len<=n;len++)
{
for(int i=0;i+len-1<n;i++)
{
int j = i+len-1;
if(len==1)
{
dp1[i][j]=true;
}
else
{
if(s[i]==s[j]&&(i==j-1||dp1[i+1][j-1]))
dp1[i][j] = true;
}
}
}
vector<int > dp2(n,INT_MAX);
for(int i=0;i<n;i++)
{
if(dp1[0][i])
dp2[i] = 0;
for(int j=0;j<i;j++)
{
if(dp1[j+1][i])
dp2[i] = min(dp2[i],dp2[j]+1);
}
}
return dp2[n-1];
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LintCode - 순차적으로 숫자를 인쇄합니다.1에서 최대 N까지의 정수를 반복하는 방법으로 찾습니다. 예제 제시N = 1, 반환[1,2,3,4,5,6,7,8,9]. 제시N = 2, 반환[1,2,3,4,5,6,7,8,9,10,11,...,99]. 주의 다음과 같...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
