[LetCode P97] Interleaving String 동적 계획
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.문제풀이 사고방식: 먼저 귀환으로 하자고 생각하면 우리는 매번 s3의 문자를 먹는다. 만약에 s1의 시작 문자가 이 문자라면 우리는 s1의 시작 문자로 매칭한다. 만약에 s2의 시작 문자가 이 문자라면 s2로 매칭하고 마지막에 두 가지 가능한 하위 문제가 있다.코드는 매우 간단합니다.
if (s3.length() == 0) return s1 == "" && s2 == "";
return (s1.length() && s1[0] == s3[0] && isInterleave(s1.substr(1), s2, s3.substr(1)))|| (s2.length() && s2[0] == s3[0] && isInterleave(s1, s2.substr(1), s3.substr(1)));그러나 이렇게 하면 시간의 복잡도가 너무 높고 최악의 경우 2^n이 있다.그래서 우리는 DP를 사용하는 것을 고려한다. 왜냐하면 상술한 문제 중 많은 하위 문제가 중복되기 때문이다.우리의 DP 수조는 길이가 j인 s1 서브 문자열과 길이가 m인 s2 서브 문자열이 인터리빙으로 j+m인 s3 서브 문자열을 형성할 수 있는지 여부입니다.상태 전이 방정식은
dp[j+1][m] = dp[j][m] && s1[j] == s3[j+m+1]dp[j][m+1]와 같은 이치로 얻을 수 있어야 한다.마지막 코드:class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s1.length() + s2.length() != s3.length()) return false;
vector<vector<bool>> dp(s1.length()+1, vector<bool>(s2.length()+1, false));
dp[0][0] = true;
for (int i = 1; i <= s3.length(); ++i)
{
// j s1 + i-j s2
for (int j = max(int(i - s2.length()), 0); j <= min(int(s1.length()), i); ++j)
{
int m = i - j;
dp[j][m] = (j > 0 && dp[j-1][m] && s1[j-1] == s3[i-1])
|| (m > 0 && dp[j][m-1] && s2[m-1] == s3[i-1]);
}
}
return dp[s1.length()][s2.length()];
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
