Interleaving String(문자열 조합, 동적 계획)[leetcoode]
For example, Given: s1 =
"aabcc" , s2 = "dbbca" , When s3 =
"aadbbcbcac" , return true. When s3 = "aadbbbaccc" , return false. 문제는 s3이 s1과 s2를 엇갈려 혼합할 수 있는지, 문자 간의 상대적인 순서는 바꿀 수 없다는 것이다.동적 기획으로 dp[i][j]는 s3의 전(i+j) 문자가 s1의 전 i 문자와 s2의 전 j 문자로 구성될 수 있는지를 나타낸다.
점차적으로 미루는 것은 그리 복잡하지 않으니 코드를 보아라.
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int l1=s1.size(),l2=s2.size(),l3=s3.size();
if(l1+l2!=l3)return false;
bool dp[1000][1000];
for(int i=0;i<=l1;++i)for(int j=0;j<=l2;++j)
{
if(i==0&&j==0)dp[0][0]=true;
else if(i==0)dp[0][j]=dp[0][j-1]&(s2[j-1]==s3[j-1]);
else if(j==0)dp[i][0]=dp[i-1][0]&(s1[i-1]==s3[i-1]);
else
{
dp[i][j]=(dp[i][j-1]&(s2[j-1]==s3[i+j-1]));
dp[i][j]|=(dp[i-1][j]&(s1[i-1]==s3[i+j-1]));
}
}
return dp[l1][l2];
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
