LC.44. 와일드카드 일치(DP)
8147 단어 DP
LC.44. 와일드카드 일치(DP)
전송문
아이디어: d p dp dp.여기는 문제풀이에 따라 다시 한 번 정리한다.
분명히 dp[i][j]dp[i][j]dp[i][j]를 sss 전 ii 문자와 pp 전 jj 문자가 일치하는지 여부를 설정할 수 있습니다.
우선 우리는 상태 이동 방정식을 고려한다.
1. 분명히 p[j-3-1]=′?′p[j-1]=='?' p[j−1]==′?′또는 s[i-3-1]=p[j-3-1]s[i-1]=p[j-1]s[i-31]=p[j-31]]는 dp[i-31][j-1]dp[i-1][j-1]dp[i-31][j-1][j-1][j-1]로 직접 옮길 수 있다.
즉, dp[i][j] = dp[i-3-1] [j-3] dp[i] [j]=dp[i-1] [j-1] dp[i] [j]=dp[i-3] [j-1].
2. p[j-1]=′p[j-1]='*'p[j-1]======′′이′이면 분명히 dp[i-1][j]와 dp[i][j-1]dp[i]와 dp[i][j-1], [j]와 dp[j][j-1]dp[i][j-1], [j-1]와 dp[j][i][j-1]로 옮길 수 있다.
즉 ∗*∗이 공백인지 여부에 대응하고 공백이 dp[i][j-3]dp[i][j-1]dp[i][j-1]로 직접 이동할 경우
그렇지 않으면 빈 문자열이 아닙니다.\*\*\임의의 문자열로 변환될 수 있기 때문에 반드시 d p [i --1] [j] dp [i-1] [j] dp [i --1] [j]로 이동할 수 있습니다.
다른 상황은 옮길 수 없다.
다시 경계 상황을 고려하면 분명히 dp[0][0] = 1, dp[i][0] = 0, (i>0)dp[0][0] = 1, dp[i][0] = 0, (i>0)dp[0] = 1, dp[i][0] = 0, (i>0)
dp[0] [i] dp[0] [i] dp[0] [i], 이전 ii의 문자가 모두 ∗*∗인지 고려해야 한다. 만약에 나타난다면??또는 알파벳은 d p [0] [i] = 0 dp[0] [i] = 0 dp[0] [i] = 0.
시간 복잡도: O(nm)O(nm)O(nm)class Solution {
public:
bool isMatch(string s, string p) {
int m=s.size(),n=p.size();
vector<vector<bool> >dp(m+1,vector<bool>(n+1));
dp[0][0]=1;
for(int i=1;i<=n;i++)
if(p[i-1]=='*') dp[0][i]=1;
else break;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(s[i-1]==p[j-1]||p[j-1]=='?') dp[i][j]=dp[i-1][j-1];
else if(p[j-1]=='*') dp[i][j]=dp[i-1][j]|dp[i][j-1];
return dp[m][n];
}
};
A C AC AC 로봇 지식 추가 정보...\dots\dots...
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)
python 풀이
DP를 이용해 풀이
보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서
고민을 했는데
이 문구 덕분에 DP 를 이용해 풀이할 수 있었다
뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다
코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
class Solution {
public:
bool isMatch(string s, string p) {
int m=s.size(),n=p.size();
vector<vector<bool> >dp(m+1,vector<bool>(n+1));
dp[0][0]=1;
for(int i=1;i<=n;i++)
if(p[i-1]=='*') dp[0][i]=1;
else break;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(s[i-1]==p[j-1]||p[j-1]=='?') dp[i][j]=dp[i-1][j-1];
else if(p[j-1]=='*') dp[i][j]=dp[i-1][j]|dp[i][j-1];
return dp[m][n];
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
