단순 정규 표현 식 이 일치 하 는 자바 구현

LeetCode 의 Problem 10 (Regular Expression Matching) 은 간단 한 버 전의 정규 표현 식 일치 문제 입 니 다.문제 의 일치 기 호 는 두 가지 만 있 는데 그것 이 바로 '...' 와 '*' 이 고 전 자 는 임의의 단일 문자 와 일치 할 수 있다.후 자 는 사용 할 때 기호 앞 에 문자 나 '.' 가 존재 하고 0 개 이상 의 문자 와 일치 하도록 확보 해 야 한다.즉, a * 는 0 개 이상 의 연속 a 와 일치 합 니 다. * 는 임의의 "." 를 대표 하기 때문에 모든 문자열 과 일치 합 니 다.제목 은 목적 문자열 s 와 일치 하 는 문자열 p 를 입력 하고 일치 하 는 결 과 를 출력 해 야 합 니 다. 즉, 성공 적 으로 일치 할 수 있 는 지 여부 입 니 다.
이 문제 에 대해 서 는 동적 계획 을 사용 하여 알고리즘 을 작성 할 수 있 습 니 다.
먼저 2 차원 상태 배열 f 를 정의 하여 모든 일치 하 는 단계 의 상 태 를 저장 합 니 다. f [i] [j] 는 일치 하 는 문자열 p 가 0 에서 j - 1 의 하위 문자열 과 일치 하 는 문자열 s 가 0 에서 i - 1 의 하위 문자열 과 일치 하 는 결 과 를 표시 합 니 다.입력 한 목적 문자열 s 와 일치 하 는 문자열 p 에 따라 각각 크기 를 얻어 m 와 n 으로 만 들 수 있 습 니 다.m 와 n 의 크기 에 따라 2 차원 상태 배열 f [m + 1] [n + 1] 을 정의 할 수 있 습 니 다.
그 다음 에 배열 의 초기 화 과정 을 진행한다.먼저 f [0] [0] 이 최초의 상 태 를 true 로 설정 합 니 다. 빈 문자열 이 빈 문자열 과 일치 하 는 것 을 의미 합 니 다. 성공 합 니 다.그리고 순환 을 통 해 배열 의 첫 번 째 열 을 false 로 초기 화 합 니 다. 즉, f [i] [0] = false 는 빈 문자열 로 목적 문자열 을 일치 시 키 는 데 실 패 했 습 니 다.이 어 첫 줄 을 초기 화해 야 한다.첫 번 째 줄 의 대표 적 인 문자열 은 빈 문자열 이 므 로 a * 와 같은 일치 하 는 결 과 를 고려 해 야 합 니 다.f [0] [1], 일치 하 는 문자열 은 하나의 문자 로 빈 문자열 과 일치 하지 않 기 때문에 false 입 니 다.첫 줄 의 나머지 부분 은 a * 인지 여 부 를 판단 하기 시 작 했 습 니 다. 일치 하 는 문자열 의 마지막 문 자 는 '*' 이 고 'a *' 이전의 일치 하 는 결 과 는 성공 해 야 true 입 니 다.즉 f [0] [j] = p [j - 1] = '*' & & f [0] [j - 2];
초기 화 후 남 은 배열 을 채 우기 시작 합 니 다.한 두 층 의 순환 을 통 해 한 줄 한 줄 씩 상 태 를 업데이트 합 니 다.
순환 할 때마다 문자열 p 의 현재 문자 p [j - 1] 이 '*' 인지 판단 해 야 합 니 다.그렇지 않 으 면 현재 문자 가 s [i - 1] 과 같 는 지, 그리고 앞의 부분 이 일치 하 는 지 판단 해 야 합 니 다.모두 true 라면 f [i] [j] = true;그렇지 않 으 면 false;
만약 p [j - 1] 이 '*' 라면 'a *' 에 대해 일치 하 는 상황 을 0 개의 a 와 여러 개의 a 두 가지 상황 으로 나 누 어 토론 해 야 한다.f [i] [j - 2] 는 0 개의 a 와 일치 하 는 결 과 를 나타 낸다.(s [i - 1] = = p [j - 2] | p [j - 2] = = ') & f [i - 1] [j] 는 여러 a 와 일치 하 는 결 과 를 나타 낸다.
순환 한 후에 필요 한 2 차원 상태 배열 을 생 성 했 는데 그 중에서 f [m] [n] 은 바로 원 하 는 일치 결과 입 니 다.
자바 방법 은 다음 과 같 습 니 다.

public static boolean isMatch(String s, String p) {
        int m = s.length(),n = p.length();
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        boolean[][] f = new boolean[m+1][n+1];
        f[0][0] = true;
        for(int i=1;i<=m;i++){
        	f[i][0] = false;
        }
        if(n != 0){
        	f[0][1] = false;
        }
        for(int j=2;j<=n;j++){
        	f[0][j] = pp[j-1] == '*' && f[0][j-2];
        }
        for(int i=1;i<=m;i++)
        	for(int j=1;j<=n;j++){
        		if(pp[j-1] != '*'){
        			f[i][j] = f[i-1][j-1] && (pp[j-1] == ss[i-1] || pp[j-1] == '.');
        		}else{
        			f[i][j] = f[i][j-2] || (ss[i-1] == pp[j-2] || pp[j-2] == '.') && f[i-1][j]; 
        		}
        	}
        return f[m][n];
    }