LeetCode \ # 10 정규 표현 식 일치 정규 표현 식 일치

10 정규 표현 식 일치 정규 표현 식 일치
Description: Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example:
Example 1:
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa" p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab" p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input: s = "aab" p = "c*a*b" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:
Input: s = "mississippi" p = "mis*is*p*." Output: false
제목 설명: 문자열 s 와 문자 규칙 p 를 드 립 니 다. '*' 를 지원 하 는 정규 표현 식 과 일치 하 는 것 을 실현 하 십시오.
'' 임의의 단일 문자 '*' 가 0 개 이상 앞 에 있 는 요소 와 일치 하 는 것 은 일부 문자열 이 아 닌 전체 문자열 s 를 포함 하 는 것 입 니 다.
설명:
s 는 비어 있 을 수 있 으 며 a - z 에서 소문 자 만 포 함 됩 니 다.p 는 비어 있 을 수 있 으 며 a - z 의 소문 자 와 문자, 그리고 * 만 포 함 됩 니 다.
예시: 예시 1:
입력: s = "aa" p = "a" 출력: false 설명: "a" 는 "aa" 전체 문자열 과 일치 할 수 없습니다.
예시 2:
입력: s = "aa" p = "a *" 출력: true 설명: '*' 는 0 개 이상 의 앞 에 있 는 요 소 를 일치 시 킬 수 있 기 때문에 여기 앞 에 있 는 요 소 는 'a' 입 니 다.따라서 문자열 'aa' 는 'a' 로 볼 수 있 습 니 다.
예시 3:
입력: s = "ab" p = ". *" 출력: true 설명: ". *" 는 0 개 이상 ('*') 임 의 문자 (') 와 일치 할 수 있 음 을 표시 합 니 다.
예시 4:
입력: s = "aab" p = "c * a * b" 출력: true 설명: '*' 는 0 개 또는 여러 개 를 표시 하기 때문에 여기 'c' 는 0 개 이 고 'a' 는 한 번 반복 된다.따라서 문자열 'aab' 와 일치 할 수 있 습 니 다.
예시 5:
입력: s = "missisippi" p = "mis * is * p *." 출력: false
생각:

두 문자열 이 일치 하면 대량의 하위 문제 가 발생 하고 동적 계획 으로 해결 할 수 있 습 니 다

먼저 dp [i] [j] 표시 s [i] 와 p [j] 일치

dp [i - 1] [j - 1] 에서 출발 하여, s [i] 와 p [j] 3.1 의 가장 간단 한 상황 을 관찰 하고, s [i] = = p [j], dp[i] [j] [j] = dp [i - 1] [j - 1] 3.2 만약 p [j] = = "", 직접 일치 할 수도 있 으 면, dp [i] [j] = dp [i - 1] [j - 1] [j - 1] 3.3 만약 p [j] = = "*", 앞 글자 와 0 개 이상 일치 하려 면 두 가지 상황 으로 나 눌 수 있 는데, 하 나 는 것 은 p [j - 1] = = [j - 1] = [j] [j]] [j]] 3.3 만약 p [j] = = = = "*", 앞 글자 가 0 개 이상 일치 하려 면 두 j - 1] = "."또한 이 종류 로 분류), 일치 할 수 있 습 니 다. dp [i] [j] = dp [i - 1] [j - 1], 다른 하 나 는 p [j - 1]! =s [i], 여 기 는 0 개의 일치 여 부 를 볼 수 있 습 니 다. dp [i] [j - 2] 를 봐 야 하기 때문에 dp [i] [j] = dp [i] [j - 2]

가 있 습 니 다.
시간 복잡 도 O (mn), 공간 복잡 도 O (mn), n, m 는 각각 s 와 p 의 길이 임 을 알 수 있 습 니 다. 여기 서 dp 두 줄 만 인접 한 것 을 사용 하면 공간 복잡 도 를 O (m) 로 줄 일 수 있 습 니 다.
코드: C + +:

class Solution 
{
public:
    bool isMatch(string s, string p) 
    {
        int n = s.size(), m = p.size();
        bool dp[n + 1][m + 1];
        for (int i = 0; i <= n; i++) for(int j = 0; j <= m; j++) dp[i][j] = false;
        dp[0][0] = true;
        for (int i = 2; i <= m; i++) if (p[i - 1] == '*') dp[0][i] = dp[0][i - 2];
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (s[i - 1] == p[j - 1] or p[j - 1] == '.') dp[i][j] = dp[i - 1][j - 1];
                if (p[j - 1] == '*') if (j > 1) dp[i][j] = ((p[j - 2] == s[i - 1] or p[j - 2] == '.') and dp[i - 1][j]) or dp[i][j - 2];
            }
        }   
        return dp[n][m];
    }
};

Java:

class Solution {
    public boolean isMatch(String s, String p) {
        return s.matches(p);
    }
}

Python:

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        return re.match(p + '$', s)