LeetCode: 10번 (Regular Expression Matching) [JAVA]

문제 링크

https://leetcode.com/problems/regular-expression-matching/

Regular Expression Matching - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 문자열 s와 패턴 p의 매치 여부를 판별하는 함수를 재귀함수로 작성
   • 기저 조건의 경우 패턴의 문자열이 비었을 때 주어진 문자열 s가 비었다면 true를 반환하고 그렇지 않다면 false 반환
   • 주어진 패턴 p에서 가장 앞의 문자(c)를 꺼내고, 이후 뒤의 문자가 다른 문자인지 *인지 확인
     • *이고 문자 c가 '.'이면 주어진 문자 s를 반복문을 통해 앞에서부터 자른 문자열들과 현재 사용하고 난 이후의 패턴 p의 부분문자열을 가지고 재귀함수를 호출하며, 이 중 맞는 답이 있다면 true 반환
     • *이고 문자 c가 일반 문자라면 주어진 문자열 s에서 해당 패턴이 맞는 부분까지 문자열들을 잘라 앞선 p의 부분 문자열과 함께 재귀함수 호출
     • *이 없고 문자 c가 '.'이면 문자열 s가 비었다면 false를 반환하지만 그렇지 않다면 s와 p를 하나씩 자른 부분문자열들을 가지고 재귀함수 호출
     • *이 없고 문자 c가 일반 문자라면 문자열 s가 비었거나 문자가 매치되지 않는다면 false 반환, 그 외에는 s와 p를 하나씩 자른 부분문자열들을 가지고 재귀함수 호출
2. 주어진 문자열 s와 p를 가지고 해당 재귀함수 호출, 그 결과를 반환

 문제 자체는 주어진 문자열과 패턴이 매치하는지 아닌지를 판별하면 되는 간단한 문제이지만, 언어에서 제공하는 정규표현식을 활용하지 않고 직접 매치 여부를 파악하는 함수를 작성해야 하기에 매우 복잡한 문제이다. 심지어 여기서 사용할 수 있는 패턴으로 '.'과 '*'이 있어, 임의의 문자와 매치되는 지와 특정 문자의 반복도 신경써야 한다.

 그런 추가 패턴들의 여부를 고려해 전체적인 풀이 방향은 재귀함수로 정하고 문제를 해결했다. 우선 재귀함수의 기저 조건은 패턴 p의 문자열이 비었을 때 주어진 문자열 s가 비었다면 true를 반환하고 그렇지 않다면 false를 반환한다. 그 다음에는 주어진 패턴 p에서 가장 앞의 문자를 꺼내 c라고 정하고, 이후 문자열을 확인해 뒤에 '*'이 있는 지 없는 지를 확인한다.

 만약 '*'이 있고 문자 c가 '.'인 경우 패턴 자체가 모든 문자와 매치되기 때문에, 주어진 문자열 s를 처음부터 끝까지 순차대로 substring() 함수를 통해 자르며 현재 사용한 패턴의 이후 부분과 같이 다음 재귀함수를 호출한다. 이 때 하나라도 맞는 재귀함수가 존재할 경우 그대로 true를 반환한다.

 그 다음 '*'이 있고 문자 c가 일반 문자인 경우 해당 문자의 나열과만 매치가 되기 때문에, 주어진 문자열 s에서 그대로 s와 p의 부분문자열을 호출하거나 문자 c와 매칭되는 부분까지의 부분문자열과 p의 부분문자열을 가지고 다음 재귀함수를 호출한다. 이 때도 하나라고 true가 반환된다면 그대로 true를 반환한다.

 '*'이 없고 문자 c가 '.'인 경우엔 단순히 문자열 s와 p에서 앞의 하나씩 제거하고 다음 재귀함수를 호출하면 되기에, 만약 s가 비어있다면 false를 반환하고 그 이외엔 맞게 재귀함수를 호출한다.

 '*'이 없고 문자 c가 일반 문자라면 주어진 문자열이 없거나 맨 앞 문자가 매치되지 않으면 false를 반환하며, 그 이외엔 앞선 경우와 같이 문자열 s와 p에서 앞의 문자를 하나씩 제거하고 다음 재귀함수를 호출하면된다.

 이렇게 작성한 함수를 isMatch()함수에서 주어진 문자열 s와 p를 인자로 호출하여, 그 결과를 반환하면 된다.

 

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

    boolean check(String s, String p) {
        if (p.length() == 0) {//기저조건
            if (s.length() != 0) {
                return false;
            } else {
                return true;
            }
        }

        char c = p.charAt(0);//패턴의 앞 문자 추출

        if (p.length() >= 2 && p.charAt(1) == '*') {//문자 + '*' 인 경우
            if (c == '.') {//'.*'인 경우
                for (int i = 0; i <= s.length(); i++) {
                    if (check(s.substring(i), p.substring(2))) {
                        return true;
                    }
                }
            } else {//'문자*'인 경우
                for (int i = 0; i <= s.length(); i++) {
                    if (i == 0) {//문자는 그대로 '문자*'만 없애서 다음 재귀함수 호출
                        if (check(s, p.substring(2))) {
                            return true;
                        }
                    } else {//문자가 맞는 부분까지 호출
                        if (c == s.charAt(i - 1)) {
                            if (check(s.substring(i), p.substring(2))) {
                                return true;
                            }
                        } else {
                            break;
                        }
                    }
                }
            }
        } else {//단순 문자만 존재
            if (c == '.') {// '.'인 경우
                if (s.length() == 0) {//주어진 문장이 없는 경우
                    return false;
                } else {//어떠한 문자든
                    return check(s.substring(1), p.substring(1));
                }
            } else {//문자인 경우
                if (s.length() == 0 || s.charAt(0) != c) {//주어진 문장이 없거나 안맞는 경우
                    return false;
                } else {//맞는 경우
                    return check(s.substring(1), p.substring(1));
                }
            }
        }

        return false;
    }
}

결과