검지 offer 19: 정규 표현 식 일치 (시퀀스 DP)

해제

제목: 정상 문자열 S 과 정규 문자열 P 을 지정 하여 똑 같은 문자열 을 표시 하 는 지 여 부 를 판단 합 니 다.

문제 풀이: 분류 토론, 우 리 는 S, P S 와 P 의 현재 위 치 를 나타 내 는 문 자 를 이용 하여 이들 의 길 이 를 각각 i 과 j 이 라 고 가정 한다.

만약 n 이 라면 판단 m 은 P[j] != . && p[j] != * 과 S[0~i]==P[0~j] 로 전환 합 니 다. 그렇지 않 으 면 현재 위치 까지 의 두 문자열 이 일치 하지 않 음 을 설명 합 니 다

.

만약 S[0~i-1] 이 라면 현재 P[0~j-1] 는 무엇이든 일치 하기 때문에 P[j]=='.' 와 S[i] 의 대비 로 전환 하면 발견 하기 어렵 지 않 고 사실은 첫 번 째 상황

을 포함 할 수 있다.

가장 어 려 운 것 은 S[0~i-1] 이다. 이때 우 리 는 P[0~j-1] 와 P[j]==* 를 직접 비교 할 수 없고 P[j] 를 하나의 전체 로 봐 야 한다. 편 의 를 위해 우 리 는 S[i] 대표 P[j-1]P[j] 를 사용한다.

이때 우 리 는 그것 c 이 P[j-1] 인지 아 닌 지 를 판단 해 야 한다.

그렇다면 S[i] 과 c 가 여전히 일치 하 는 지 확인

그렇지 않 으 면 S[0~i-1] 0 번 을 뽑 을 때 만 일치 할 수 있 고, 이렇게 되면 문 제 는 P[0~j] 와 c* 의 일치 로 바뀐다.

상 태 는 다른 문자열 의 동적 계획 문제 와 마찬가지 로 2 차원 배열 S[0~i] 대표 P[0~j-2] 와 dp[i][j] 의 일치 상황 을 이용 하고 마지막 상황 은 S[0~i]

이 라 고 밝 혔 다.

초기 상태: 여기 서 비교적 명확 한 초기 상 태 를 고려 해 야 한다.

P[0~j]: 의심 할 여지없이 정확 하 다. 왜냐하면 이것 은 공 대공

이기 때문이다.

dp[n][m]: 판단 이 필요 합 니 다. dp[0][0] 빈 문자열 과 일치 할 수 있 기 때 문 입 니 다. 예 를 들 어 dp[0][x>0] 은 0 회 P[0~x]

를 대표 할 수 있 습 니 다.

a*: 잘못된 것 입 니 다. a 일반 문자열 이기 때문에 빈 문자열

과 일치 하지 않 습 니 다.

상태 이동:

상황 1, 2: dp[x>0][0]

상황 3:

S : dp[i][j] = dp[i-1][j-1] && (S[i]==P[j])

S[i] != P[j-1] : dp[i][j] == dp[i][j-2]

실현: 시퀀스 dp 팁, 문자열 앞 에 하나 S[i] == P[j-1] 를 추가 하여 경계 에 대한 고려 를 줄 입 니 다

class Solution {
    public boolean isMatch(String s, String p) {
        s = ' '+s;
        p = ' '+p;
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[1+n][1+m];

        char[] sc = s.toCharArray();
        char[] pc = p.toCharArray();
        dp[0][0] = true;
        for(int i = 1;i < n;i++){
            dp[i][0] = false;
        }
        for(int j = 2;j < m;j+=2){ 
            if(pc[j] == '*') dp[0][j] = dp[0][j-2];  
        }
        for(int i = 1;i < n;i++){
            for(int j = 1;j < m;j++){
                if(pc[j]!='*'){
                    if(pc[j] == '.' || pc[j]==sc[i]) 
                        dp[i][j] = dp[i-1][j-1];
                }
                else{
                    if(j >= 2) dp[i][j] |= dp[i][j-2];
                    if(pc[j-1] == sc[i]||pc[j-1]=='.') dp[i][j] |= dp[i-1][j];
                }
            }
        }
        return dp[n-1][m-1];
    }
}

제목.

정규 표현 식 일치