leetcode-44. Wildcard Matching

이 문제는 이전의 Regular Expression Matching과 약간 비슷하다. 첫 번째 반응은 이전과 마찬가지로 귀속으로 하는 것이다

bool doMatch(char *s,char *p)
{
    if (*p == '\0')    return *s == '\0';
    if(*p == '*')
    {
        while(*s!='\0')// 0 ，1 ····
        {
            if(doMatch(s,p+1))
                return true;
            s++;
        }
        // 
        return doMatch(s,p+1);
    }
    else
    {
  //      if(*p!=*s && *p!='.')   return false;
  //      return doMatch(s+1,p+1);
        if (*p == *s || (*p == '?' && *s != '\0'))  
        return doMatch(s+1, p+1);  
        return false;  

    }
}
bool isMatch(char* s, char* p) {
    if(*p=='\0')    return *s=='\0';
    char *new_p = (char *)malloc(strlen(p));
    int j=0;
    // p ， * 
    for(int i=0;i<strlen(p);i++)
    {
        if(i>0 && p[i]=='*' && p[i-1]=='*')
            continue;
        new_p[j] = p[i];
        j++;
    }
    new_p[j] = '\0';
    return doMatch(s,new_p);
}

시간 초과...중복 비교가 발생했기 때문이다.예를 들어 p='c*ab*c', s='cddabbac', 첫 번째 *를 만났을 때 p의 나머지 부분'ab*c'와 s의 나머지 부분'ddabbac'를 귀속 처리해야 한다.두 번째 *가 발생하면 나머지 부분을 비교해야 하기 때문에 동적 계획으로 중복된 하위 문제를 제거해야 한다.
dp[i][j]는 p[i-1]과 s[j-1]까지 일치하기 때문에 현재 문자가 *일 때 dp[i][j]=dp[i-1][j]|dp[i][j-1]|dp[i][j-1]|dp[i-1][j-1]
현재 문자가 다른 경우 dp[i]pj]=dp[i-1][j-1] & (p[i-1]='?'|p[i-1]=s[j-1])
여기에 초기값을 설정하기 편리하도록 한 줄과 한 열을 추가하고 dp[0][0]=true를 설정합니다.
우리는 dp의 값이 앞줄과 앞열에만 관계가 있다는 것을 알아차렸기 때문에 수조를 두 줄로 줄여 공간을 절약할 수 있다.

class Solution {
public:
    bool isMatch(string s, string p) {
        int s_len = s.length();
        int p_len = p.length();
        vector<vector<bool>>dp(2,vector<bool>(s_len+1,false));
        dp[0][0] = 1;
        for(int i=1;i<=p_len;i++)
        {
            int cur=i%2;
            int prev=(i+1)%2;
            dp[cur][0]=dp[prev][0]&&p[i-1]=='*'; 
            for(int j=1;j<=s_len;j++)
            {
                if(p[i-1]=='*')
                    dp[cur][j] = dp[cur][j-1] || dp[prev][j] ||dp[prev][j-1];
                else 
                    dp[cur][j] = dp[prev][j-1] && (p[i-1]=='?' || p[i-1]==s[j-1]);
            }
        }
        return dp[p_len%2][s_len];
    }
};