leetcode10+leetcode44 정규 일치 문제 요약

정규 일치 문제형 총결산

이 두 문제는 사실 모두 일치 유형에 속하는 문제이다. 모두'*'는 여러 문자를 임의로 일치할 수 있다는 것을 표시하고 하나는'있다. '단일 문자와 일치할 수 있음을 나타냅니다.
비교적 생각하는 귀속 사고방식: 귀속 사고방식은 주로 두 가지가 있는데 하나는 앞뒤로 일치하는 것이고 하나는 뒤에서 앞으로 일치하는 것이다.대부분의 경우 두 가지 모두 가능합니다. 저는 여기서 주로 앞뒤로 일치하는 것을 사용합니다. 그래서 제가 정의한 dp[i][j]는 s의 i번째 문자 이후와 p의 j번째 문자 이후에 서로 일치할 수 있는 확률입니다.
이렇게 하면 논리가 비교적 명확해진다. 초기화 dp[i][j]는 모두 -1이고 방문한 적이 없고 기록이 없다는 것을 나타낸다.그리고 매번 귀속할 때 먼저 종점에 도착했는지 판단하고 p가 종점에 도착했는지 판단한 다음에 s가 종점에 도착했는지 판단한 다음에 방문한 적이 있는지 확인하고 기억화 검색을 한다.
그다음에'*'가 있는지 볼게요.
없으면 퍼스트 매칭이 있습니다. 매칭이 끝나면 후속 매칭을 진행합니다. 리턴할 때 dp[i][j]를 기록해야 합니다.
만약에 있다면 두 가지 상황으로 나뉘는데 하나는'*'가 전혀 작용하지 않으면 p가 직접 후퇴하고 하나는 p가 작용한다. 그러면 p는 이때 후퇴하지 않지만 s는 후퇴한다. 이렇게 다음 귀속을 진행할 때는'*'가 있다.
여기 이 p는 하나만 뒤로 물러나는 게 중요해!우리는 끊임없이 매칭을 시도하기 때문에 매번 하나만 매칭할 수 있습니다. 제가 처음 썼을 때 여러 개를 연속으로 매칭해서 오류가 발생했습니다. 여기서 특히 주의하세요!

leetcode 10

dp[i][j]는 s[i], p[j]부터 향후 일치 여부를 나타냅니다. s[i], p[j] 포함

class Solution {
public:
vector<vector<int>>dp;

bool DP(string& s, string& p, int i, int j, vector<vector<int>>& dp) {
	int lens = s.size();
	int lenp = p.size();

	// p ， p ， s ， 
	if (j == lenp) {
		bool ans = (i == lens);
		dp[i][j] = ans;
		return dp[i][j];
	}
	if (dp[i][j] != -1)return dp[i][j];

	// 
	bool first = false;
	if (i<lens) {
		if (s[i] == p[j] || p[j] == '.') {
			first = true;
		}
	}

	if (j<(lenp - 1) && p[j + 1] == '*') {
		//bool situation1 = DP(s, p, i, j + 2, dp);
		//bool situation2 = first&&DP(s, p, i + 1, j, dp);
		//dp[i][j] = situation1 || situation2;
		//return dp[i][j];
		return dp[i][j] = (DP(s, p, i, j + 2,dp) || first == true && DP(s, p, i + 1, j,dp));
	}
	else {
		//bool situation3 = DP(s, p, i + 1, j + 1, dp);
		//dp[i][j] = first&&situation3;
		//return dp[i][j];
		return dp[i][j] = (first && DP(s, p, i + 1, j + 1,dp));
	}
}

bool isMatch(string s, string p) {
	int n = s.size();
	int m = p.size();
	//vector>dp(n+1, vector(m+1, -1));
	dp.assign(s.size() + 1, vector<int>(p.size() + 1, -1));
	bool ans = DP(s, p, 0, 0, dp);
	return dp[0][0];
}
};

leetcode 44

dp[i][j]는 s[i], p[j]부터 향후 일치 여부를 나타냅니다. s[i], p[j] 포함

class Solution {
public:
    bool DP(string& s,string& p,int i,int j,vector<vector<int>>& dp){
        // dp[i][j] s i p j 
        int lens=s.size();
        int lenp=p.size();
        if(j==lenp){
            return dp[i][j]=i==lens;
        }
        if(i==lens){
            for(int k=j;k<lenp;k++){
                if(p[k]!='*'){
                    return dp[i][j]=false;
                }
            }
            return dp[i][j]=true;
        }
        if(dp[i][j]!=-1)return dp[i][j];
        if(p[j]!='*'){
            bool first=(p[j]==s[i]||p[j]=='?') ;
            return dp[i][j]=first&&DP(s,p,i+1,j+1,dp);
        }
        return dp[i][j]=DP(s,p,i+1,j,dp)||DP(s,p,i,j+1,dp);
    }
    bool isMatch(string s, string p) {
        int m=s.size();
        int n=p.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,-1));
        DP(s,p,0,0,dp);
        return dp[0][0];
    }
};