leetcode 10

문자열 지정 s 와 문자 모드 ( p )。지 지 를 실현 하 다  '.'  화해시키다  '*'  정규 표현 식 이 일치 합 니 다.

'.'         。
'*'             。

일치 하 는 문자열 을 덮어 써 야 합 니 다. s 일부 문자열 이 아 닙 니 다.
설명:

s  이 가능 하 다, ~ 할 수 있다,...  a-z  라 는 소문 자 를 썼 다.

p  이 가능 하 다, ~ 할 수 있다,...  a-z  소문 자  .  화해시키다  * 。

예시 1:

  :
s = "aa"
p = "a"
  : false
  : "a"      "aa"      。

예시 2:

  :
s = "aa"
p = "a*"
  : true
  : '*'                ,       'a' 。  ,    'a'   ,        "aa"。

예시 3:

  :
s = "ab"
p = ".*"
  : true
  : ".*"           ('*')    ('.')。

예시 4:

  :
s = "aab"
p = "c*a*b"
  : true
  : 'c'       , 'a'        。          "aab"。

예시 5:

  :
s = "mississippi"
p = "mis*is*p*."
  : false

사고방식: 정규 문자열 과 일치 하 는 코드 사고방식 은 매우 단일 하 다. 바로 폭력 이지... 그리고 자신 이 시간 을 초과 했다 는 것 을 알 게 되 었 다. = 그리고 자신 이 너무 폭력 적 이라는 것 을 알 게 되 었 다. 그리고 기억 화 검색 에 들 어가 면 바로 지나 간다. 즉, dp 이다. 그러나 이 문 제 는 dp 로 쓰기 가 쉽 지 않 고 생각 이 조금 부족 하면 틀 렸 다. 아니면 나의 기억 화 검색 이 비교적 믿 을 만하 다.폭력 검색 에 dp 를 더 해서 기억 하면 돼 요.그러나 저 는 최 적 화 된 것 이 아 닙 니 다. 일치 하 는 문자열 은 중복 되 는 쓸모없는 일치 항목 을 많이 포함 할 수 있 기 때 문 입 니 다. leetcode 의 최 적 화 는 먼저 일치 하 는 문자열 을 최적화 시 킨 다음 에 직접 검색 을 하 는 것 입 니 다. 기억 화 된 검색 을 할 필요 가 없습니다. 주로 일치 하 는 문자열 을 최적화 한 후에 매우 큰 가 지 를 잘 랐 습 니 다.검색 공간 을 대폭 줄 여 기억 화 검색 을 하지 않 아 도 된다.

static int x = []() { 
    std::ios::sync_with_stdio(false); 
    cin.tie(NULL);  
    return 0; 
}();

int dp[50][50];
bool match(string& a, int la, string& b, int lb)
{
    if (dp[la][lb] != -1)
    {
        return dp[la][lb];
    }
    if (la == a.length() && lb == b.length())
    {
        return dp[la][lb] = true;
    }

    if (la > a.length() || lb > b.length())
    {
        return dp[la][lb] = false;
    }

    if (lb + 1 < b.length() && b[lb + 1] == '*')
    {
        bool stat1 = false, stat2 = false, stat3 = false;

        stat1 = match(a, la, b, lb + 2);

        if (b[lb] == '.' || a[la] == b[lb])
        {
            stat2 = match(a, la + 1, b, lb + 2);
            stat3 = match(a, la + 1, b, lb);
        }

        if ( stat1 || stat2 || stat3 )
        {
            return dp[la][lb] = true;
        }
        else
        {
            return dp[la][lb] = false;
        }
    }

    if (b[lb] != '.' && a[la] != b[lb])
    {
        return dp[la][lb] = false;
    }

    
    return dp[la][lb] = match(a, la + 1, b, lb + 1);
}

class Solution {
public:
    bool isMatch(string s, string p) {
        memset(dp,-1,sizeof(dp));
        if (match(s, 0, p, 0))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};