LeetCode 10_Regular Expression Matching

또 이틀 동안 업데이트 되 지 않 았 습 니 다. 이틀 동안 게 으 름 을 피 운 것 이 아니 라 어 려 운 문제 에 부 딪 혔 습 니 다. 이틀 동안 이 문 제 를 계속 생각 하고 있 습 니 다. 오늘 은 끝 냅 시다.
이것 은 leetcode 의 10 번 문제 입 니 다. 난이 도 는 hard 입 니 다. leetcode 에서 난이도 가 가장 높 은 문제 입 니 다. 지난 하 드 문 제 는 이상 적 으로 풀 지 못 했 기 때문에 시간 을 많이 써 서 이 문 제 를 해결 하려 고 했 지만 일이 뜻 대로 되 지 않 았 습 니 다. 이틀 동안 의 시간 투입 도 테스트 에 통과 하지 못 하고 나중에 포기 할 수 밖 에 없 었 습 니 다.그러나 포기 하 는 것 은 시간 이 많이 걸 리 거나 지 겹 게 만 들 었 기 때 문 이 아니 라 그 당시 코드 가 200 줄 에 가 까 워 졌 고 실행 되 지 않 았 기 때문에 여러 가지 '패 치' 오류 가 있 었 기 때문이다.뭐라고 해 야 할 까? 알고리즘 은 대체적으로 생각 하 는 데 하루 도 걸 리 지 않 았 고 '패 치' 의 시간 은 알고리즘 디자인 과 인 코딩 시간 을 초과 했다. 즉, 며칠 더 노력 해서 프로그램 이 디 버 깅 을 통과 하 더 라 도 패 치 에 패 치 를 붙 였 고 심지어 일부 bug 는 아직 테스트 되 지 않 았 다.이런 상황 에서 포 기 를 선택 한 것 은 노력 하지 않 고 노력 하지 않 는 문제 가 아니 기 때 문 입 니 다. 분명히 알고리즘 디자인 이 틀 렸 기 때 문 입 니 다!정확 한 알고리즘 은 패 치 를 많이 하지 않 을 뿐만 아니 라, 시험 적 으로 만들어 서 는 안 된다.이렇게 많은 말 을 했 는데 단지 이 물건 을 계산 하지 못 하면 틀림없이 알고리즘 을 잘 배우 지 못 한 것 이다. 네가 프로 그래 밍 언어 를 잘 배우 지 못 한 것 이 아니 라 문 제 를 찾 는 관건 이 야 말로 문 제 를 해결 하 는 전제 이다.
잔말 말고 문 제 를 풀 어 라.
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).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

이 문 제 는 리 눅 스 시스템 을 배 운 사람 이 비교적 익숙 할 것 이다. 물론 다른 곳 에서 도 볼 수 있다.정규 표현 식 은 매우 유용 한 도구 이다. 이 문 제 는 그 중의 일부 일치 체 제 를 실현 하 는 것 을 고찰 하 는 것 이다.물론 그 중의 일부분 일 뿐 정규 표현 식 을 들 어 본 적 이 없어 도 제목 의 뜻 을 이해 할 수 있다.여기 서 문제 가 있 는 것 은 'ab' 와 '. *' 라 는 두 글자 가 왜 일치 하 는 지 입 니 다. 이것 은 제목 이 이해 하 는 문제 입 니 다. '*' 는 앞의 0 개 또는 여러 글자 와 일치 할 수 있 습 니 다. 이 말 은 뒤의 문자열 을 대상 으로 하 는 것 입 니 다. 즉, '. *' 중의 '*' 는 앞의 0 개 또는 여러 개 '와 일치 할 수 있 습 니 다.' 가 아니 라 '.' 실례 화 된 문자 입 니 다. 좀 더 직 설 적 으로 말 하면 '*' 입 니 다.여러 개 로 사용 할 수 있다.
문제 의 뜻 을 이해 하면 제 잘못된 생각 을 말씀 드 리 겠 습 니 다. 제 가 알고리즘 과정 을 체계적으로 배 운 적 이 없 기 때 문 입 니 다. 제 문제 풀이 방향 은 이 부분 을 대표 할 수 있 을 것 입 니 다. 제 잘못 을 분석 함으로써 여러분 들 이 자신 만 의 '정 답' 을 찾 을 수 있 기 를 바 랍 니 다.
두 문자열 은 그들의 '상등' 관 계 를 비교 합 니 다. 이 두 가 지 는 저 를 일치 하 는 문제 풀이 사고 로 이 끌 었 습 니 다. 즉, 문자열 이 같은 사 고 를 여기에 옮 기 고 일치 하 는 것 을 특수 한 상황 으로 제거 하 는 것 입 니 다.그 러 다 보 니 먼저 (사실 오 랜 시간 이 걸 렸 다) '. *' 의 특수성 이 생각 났 다. 이 를 통 해 문자열 을 분해 한 다음 에 '*' 로 더 분해 하고 싶다.이런 것들 은 더 이상 말 하지 않 겠 습 니 다. 앞에서 설명 한 바 와 같이 이런 방법 은 잘못된 것 입 니 다. 정확 한 해결 을 얻 기 어렵 습 니 다. 디 버 깅 과정 은 마치 불 을 끄 는 것 과 같 습 니 다. 어디 에 있 으 면 어디 에 물 을 주 고 어디 에 있 는 지 모 르 겠 습 니 다.
다른 말 을 해도 소 용 없어 요. 바로 대 신의 코드 로 올 라 가세 요. (여기 서 dong. wang. 1694 의 코드 공유 와 상세 한 해답 에 감 사 드 립 니 다)

</pre><pre name="code" class="cpp">class Solution {

public:
    bool isMatch(string s, string p) {
        int sSize = s.size(), pSize = p.size(), i, j;
        bool checked[sSize+1][pSize+1];
//        fill_n(&matched[0][0], (sSize+1)*(pSize+1), false);

        for(j=2, checked[0][0]=true, checked[0][1]= false; j<=pSize; ++j) // match s[0..0]
            checked[0][j] = p[j-1] == '*'? checked[0][j-2]  : false;
        for(i=1; i<=sSize; ++i)
        for(j=1, checked[i][0]=false; j<=pSize; ++j)
        {
            if(p[j-1]=='*') // case (1)
                checked[i][j] = (j>1) && ( checked[i][j-2]  ||                                                                                 ( ( checked[i-1][j]) && (s[i-1]== p[j-2] || p[j-2] == '.')) );
            else // case (2)
                checked[i][j] = checked[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');        
        }
        return checked[sSize][pSize];
    }
};

앞에서 말 했 듯 이 제 가 성공 하지 못 한 코드 는 200 줄 에 가 까 워 졌 습 니 다. 대신 의 코드 를 보면 제 가 포기 한 이유 가 있다 는 것 을 아 시 겠 죠?다음은 대 신의 알고리즘 을 설명 하 겠 습 니 다. 참고 로 이 대 신 은 자신 이 두 가지 알고리즘 코드 를 썼 습 니 다. 다른 사람들 도 좋 은 코드 가 많 고 생각 도 다 릅 니 다. 여러분 이 관심 이 있 는 것 은 leetcode 사이트 에 가서 보 세 요. 여기 서 하 나 를 대표 로 말씀 드 리 겠 습 니 다.
알고리즘 의 핵심 은 checked 라 는 2 차원 표를 구축 하 는 것 입 니 다.표 에 저 장 된 것 은 모두 이 진수 1 또는 0 (true 또는 false) 입 니 다.그럼 checked [i] [j] 즉 표 의 i 행 j 열 은 1 또는 0 으로 무엇 을 대표 합 니까?이것 은 s [0] - s [i] (s [i], 즉 s 중의 i 개 요 소 를 포함 하지 않 음) 와 p [0] - p [j] (의미 가 이전 과 같 음) 를 대표 하여 일치 하 는 지 여 부 를 나타 낸다.예 를 들 어 s = "aab", p = "c * a * b" 를 넣 으 면 checked [2] [3] 는 "aa" 와 "c * a" 가 일치 하 는 지 여 부 를 말 하 는 것 이다. 분명히 이것 은 일치 하지 않 는 다. 즉, checked [2] [3] = 0 은 checked [2] [4] = 1 과 유사 하 다. 한 마디 로 이런 뜻 이다.
쉽게 얻 을 수 있 습 니 다. checked [s. size () + 1] [p. size () + 1] 의 값 은 돌아 갈 답 입 니 다.그럼 다음은 이 표를 작성 하 는 것 입 니 다. 우 리 는 처음부터 말 합 니 다.
(1) 우선, 우리 가 먼저 표 의 첫 줄, 즉 checked [0] [j] (j = 0, 1,...) 를 작성 합 니 다.그러면 첫 번 째 는 checked [0] [0] 입 니 다. checked [i] [j] 의 의 미 를 통 해 checked [0] [0] = 1 (두 빈 문자열 이 똑 같 을 것 입 니 다) 을 쉽게 얻 을 수 있 습 니 다. checked [0] [1] = 0 (한 글자 가 빈 문자열 과 일치 할 수 없습니다) 과 유사 합 니 다.여기 서 우 리 는 checked [0] [j] 가 사실은 p 의 전 j 요소 가 빈 문자열 과 일치 하 는 지 알 수 있다.앞의 두 개 는 이미 알 고 있 습 니 다. 우 리 는 세 번 째 와 그 이후 의 시작 (가설 이 앞의 j 개 라 고 가정 하고 그 아래 에 j - 1 이 라 고 표시 하 는 것 을 주의 하 세 요). 이것 은 두 가지 상황 을 얻 을 수 있 습 니 다. 만약 에 p [j - 1] = '*' 이 라면 이 '*' 는 앞의 하 나 를 없 앨 수 있 습 니 다 (0 개의 앞 문 자 를 표시 할 수 있 기 때 문 입 니 다). 없 앤 후에 그 진 가 는 앞의 진 가 를 없 애 는 것 과 같 습 니 다.즉, checked [0] [j] = checked [0] [j - 2];만약 p [j - 1]! = '*',그것 은 분명히 마지막 으로 이 p [j - 1] 을 없 앨 수 없다. 그러면 빈 문자열 과 일치 하지 않 을 것 이다. 즉, checked [0] [j] = false 이다.이렇게 유추 하면 표 의 첫 줄 을 얻 을 수 있다.
(2) 그리고 우 리 는 표 의 첫 번 째 열 을 작성 한다.(이런 규칙 에 따라 표를 작성 하 는 알고리즘 은 일반적으로 경계 입력 을 분석 하여 표 의 가장 자 리 를 작성 하 는 것 이다) 첫 번 째 열 에 있 는 첫 번 째 줄 은 이미 작성 되 었 고 아래 의 것 도 비교적 간단 하 다. checked [0] 는 p 가 빈 문자열 일 때 s 가 언제 일치 하 는 지 를 나타 내기 때문에 s 에 문자 만 있 으 면 일치 하지 않 기 때문에 i > 0 시 checked [0] 은 모두 0 이다.즉 표 의 첫 번 째 열 은 첫 번 째 행위 1 을 제외 하고 모두 0 이다.
(3) 마지막 으로 우 리 는 마지막 checked [i] [j] 의 작성 규칙 을 찾 아야 한다.checked [0] [j] 를 작성 할 때 와 마찬가지 로 우 리 는 두 가지 상황 으로 나 누 어 고려 합 니 다. 만약 에 p [j - 1] = '*' 가 있다 면 하 나 는 앞의 문 자 를 없 애 는 것 입 니 다. 즉, checked [i] [j] = checked [i] [j - 2] 입 니 다. 이런 상황 은 '*' 앞의 문 자 를 없 애 는 것 입 니 다. 나머지 부분 이 일치 하 는 지 여 부 는 예전 의 일치 여부 에 달 려 있 습 니 다.두 번 째 는 없어 지지 않 았 습 니 다. '*' 를 사용 한 후에 도 일치 할 수 있 습 니 다. 이런 상황 에서 '*' 는 하나 이상 의 문자 로 충당 되 었 지만 구체 적 으로 얼마 인지 알 수 없 기 때문에 이 때 는 checked [*] [j - 2] 를 판단 할 수 없습니다. '*' 가 얼마나 적은 문자 로 충당 되 었 는 지 모 르 기 때문에 제거 한 후에 앞의 일치 하 는 위 치 를 모 릅 니 다.이렇게 말 하면 여러분 이 이해 할 수 있 을 지 모 르 겠 습 니 다. 예 를 들 어 s = "abbbbbbbbc", p = "ab * c" 는 분명히 이 두 꼬치 가 일치 하 는 것 입 니 다. 그러나 표를 작성 하 는 과정 에서 j 가 c 를 가리 킬 때 "b *" 를 없 애 면 나머지 a 는 s 첫 번 째 와 만 일치 할 수 있 고 중간 에 있 는 b 가 얼마나 되 는 지 모 릅 니 다. 즉, checked [*] [j - 2] 중의 * 는 i 에서 얼마나 빼 서 얻 은 것 인지 모 릅 니 다.한 마디 로 하면 '*' 는 반드시 남아 야 한다. 즉, checked [*] [j] 를 판단 해 야 한다. 우 리 는 다른 측면 에서 표 작성 문 제 를 고려 해 야 한다. 즉, 열 에 따라 표를 작성 해 야 한다. 그러면 p 는 고정된 끝 이 '*' 인 문자열 이 고 이미 알 고 있 는 '*' 는 적어도 한 글자 가 되 었 다. 그 다음 에 s 중의 문 자 를 하나씩 증가 시 켜 p 와 일치 하 는 지 여 부 를 보 는 것 이다.분명히 추 가 된 문자 가 "*" 로 대체 할 수 있 는 문자 일 때 만 일치 합 니 다. 앞의 문 자 는 checked [i - 1] [j] 입 니 다. 즉, i 번 째 데 이 터 를 추가 하기 전에 두 개 는 일치 하고 추 가 된 문 자 는 "*" 로 대체 할 수 있 는 (s [i - 1] = p [j - 2] | p [j - 2] = "입 니 다.이 점 은 좀 많이 말 했 습 니 다. 다음은 마지막 문자 가 '*' 가 아 닌 상황 입 니 다. 이 상황 은 비교적 간단 합 니 다. 마지막 으로 '실체' 를 추 가 했 습 니 다. 분명히 추 가 된 이 실 체 는 s 중의 마지막 과 일치 하고 실 체 를 증가 하기 전에 일치 해 야 합 니 다.
뒤에 있 는 checked [i - 1] [j] 곳 은 이해 하기 어 려 울 수 있 습 니 다. 여러분 은 열 에 따라 표를 작성 하고 왜 줄 을 누 르 지 못 하 는 지 많이 생각해 보 세 요. 이것 은 확실히 어렵 습 니 다.
그리고 무슨 말 을 할 까? 문 제 를 푸 는 소감 을 말 해 봐.저 는 아 이 큐 가 괜찮다 고 생각 합 니 다. 평소에 도 이런 문 제 를 깊이 연구 하지만 뭐라고 해 야 할 까요? 컴퓨터 학과 학생 이 아니 기 때문에 알고리즘 디자인 의 이론 을 배 운 적 이 없고 자신 만 의 열정 으로 문 제 를 풀 고 있 습 니 다.이렇게 하면 전공 과 큰 차이 가 있 습 니 다. 그래서 이런 말 을 하 는 것 은 여러분 에 게 학습 방향 을 찾 는 것 입 니 다. 알고리즘 을 잘 하려 면 마음 을 가 라 앉 히 고 알고리즘 이론 을 배 워 야 합 니 다.자신의 작은 총명 함 으로 멀리 가지 않 을 것 이다. 나 는 지금 이미 알고리즘 같은 책 을 읽 기 시작 했다.물론 배 울 것 이 너무 많 습 니 다. 여러분 은 자신의 방향 을 잘 찾 고 많이 노력 하면 됩 니 다.
오늘 도 기분 이 좋 지 는 않 지만, 타락 하지 않 고 꾸준히 쓰 고 있 는 것 이 다행 이 며, 언젠가 자신의 꿈 을 이 룰 수 있 기 를 바 랍 니 다.견지 하 는 모든 사람들 이 자신의 꿈 을 이 루 기 를 바 랍 니 다.