LeetCode: 44번 (Wildcard Matching) [JAVA]

문제 링크

https://leetcode.com/problems/wildcard-matching/

Wildcard Matching - LeetCode

풀이

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

1. dp용 이차원 배열 선언 (s의 길이+1, p의 길이+1)
2. 재귀 기반 패턴 매칭 함수 선언
   1) 파라미터 - 문자열 s, 문자열 s에 대한 인덱스(indexS), 문자열 p, 문자열 p에 대한 인덱스(indexP)
   2) dp 값이 존재하면 해당 값 반환
   3) indexS와 indexP가 각각 s와 p 길이 만큼 도달하면 정답 반환. 둘 중 하나만 도달하면 기본적으로 false 반환이지만, indexS가 도달하고 만약 indexP 위치의 문자가 '*'이라면 다음 위치 탐색을 시도
   4) 이후엔 indexP 위치의 문자에 대해 적절하게 처리해 다음 함수 호출
3. 결과를 바탕으로 true or false 반환

 문제에 대한 요지는 문자열 s와 패턴 p에 대해 둘이 맞는지를 체크해 반환하는 문제이다. 문제를 봤을 때 패턴 '*'로 인해 다양한 상황이 나올 수 있어, 이를 재귀로 처리하고자 문제를 재귀 기반 함수를 통해 처리하고자 했다. 다만 이후 시간초과가 발생하여, 추가로 dp를 적용했다.
 우선 dp를 위한 이차원 배열을 크기가 s의 길이+1, p의 길이+1로 선언한다. 그 다음 패턴 매칭을 확인하는 재귀 기반 함수 check를 선언한다. 파라미터로는 문자열 s, 문자열 s에 대한 인덱스(indexS), 문자열 p, 문자열 p에 대한 인덱스(indexP)를 가진다. 우선 indexS와 indexP를 바탕으로 dp에 값이 존재하면 이를 반환하고, indexS와 indexP가 각각 s와 p 길이만큼 도달하면 정답을 반환한다. 다만 이 때 둘 중 하나만 도달하면 기본적으로 false를 반환하지만, 만약 indexS가 끝에 도달했지만 indexP 위치의 문자가 '*'이라면 다음 위치로 탐색을 시도한다. 이후엔 indexS 위치의 문자와 indexP 위치의 문자를 바탕으로 적절한 처리를 시도한다. '*'이라면 indexS를 현 위치부터 끝까지 모두 옮겨가며 다음 함수를 호출해 하나라도 맞는다면 정답을 반환하고, 아니면 실패를 반환한다. '?'이라면 무조건적으로 다음 위치에 대해 함수를 호출하고, 문자라면 각각의 문자가 맞는지 아닌지에 따라 처리한다.
 그렇게 구현한 check 함수를 호출해 결과를 받고, 해당 결과에 따라 true나 false를 반환하면 된다.

 

class Solution {
    int[][] dp;//dp용 배열
    public boolean isMatch(String s, String p) {
        dp = new int[s.length() + 1][p.length() + 1];

        if (check(s, 0, p, 0) == 1) {//결과 반환
            return true;
        } else {
            return false;
        }
    }

    int check(String s, int indexS, String p, int indexP) {
        if (dp[indexS][indexP] != 0) {//dp값이 존재한다면
            return dp[indexS][indexP];
        }

        if (indexS == s.length() && indexP == p.length()) {//양쪽 문자열 모두 소모
            return dp[indexS][indexP] = 1;
        }

        if (indexP == p.length()) {//패턴만 먼저 소모
            return dp[indexS][indexP] = -1;
        }

        if (indexS == s.length()) {//문자열 먼저 소모
            if (p.charAt(indexP) == '*') {//패턴이 *이라면
                return dp[indexS][indexP] = check(s, indexS, p, indexP + 1);
            } else {
                return dp[indexS][indexP] = -1;
            }
        }

        int result = -1;

        if (p.charAt(indexP) == '*') {
            for (int i = indexS; i <= s.length(); i++) {//현재부터 끝까지 s를 잘라 탐색
                if (check(s, i, p, indexP + 1) == 1) {
                    result = 1;
                    break;
                }
            }
        } else if (p.charAt(indexP) == '?') {
            result = check(s, indexS + 1, p, indexP + 1);
        } else {
            if (s.charAt(indexS) == p.charAt(indexP)) {//서로 앞의 문자가 맞다면
                result = check(s, indexS + 1, p, indexP + 1);
            }
        }

        return dp[indexS][indexP] = result;
    }
}

결과