문제

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

• '?' Matches any single character.
• '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

제한사항

• 0 $\leq$ s.length, p.length $\leq$ 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, '?' or '*'.

접근1(시간 초과)

가장 큰 난제가 *에 대한 처리였어요. 처음 접근한 방식은 *이 발견된 시점을 시작으로, 끝부터 해당 시점까지 문자열이 매칭되는지 확인하는 방식으로 했어요. 역시나 시간 초과했어요.

답안

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

    private boolean isValidPatternForEmptyString(String p, int start){
        for(int i = start; i < p.length(); ++i){
            if(p.charAt(i) != '*'){
                return false;
            }
        }
        return true;
    }

    private boolean isMatch(String s, String p, int startS, int startP){

        int i = startS, j = startP;
        while(i < s.length() && j < p.length()){
            switch(p.charAt(j)){
                case '?':{
                    ++i; ++j;
                } break;
                case '*':{
                    while(j < p.length() - 2 && p.charAt(j) != '*'){
                        j++;
                    }
                    while(i < s.length() && false == isMatch(s, p, i, j + 1)){
                        ++i;
                    }
                    ++j;
                } break;
                default:{
                    if(s.charAt(i) != p.charAt(j)){
                        return false;
                    }
                    ++i; ++j;
                } break;
            }
        }

        if(i >= s.length() && j < p.length())
            return isValidPatternForEmptyString(p, j);
        return (j >= p.length() && i >= s.length());
    }
}

접근2

결국에 인도 형님을 유튜브에서 찾아 답을 도출해냈어요...하지만 이해했어요! DP를 활용해서 풀이하셨더라고요. 물론, 이보다 빠른 방식이 있지만 현재 제 입장에선 DP에 익숙해지는 것이 먼저다!라고 생각해서 해당 답을 참고했어요.

결론부터 말씀드리면, s를 행으로, p를 열로 전개한 2차원 배열을 구성했어요. 다만 각 행과 열에 +1을 주었죠. 왜냐하면 *는 빈 값도 true가 되는 경우가 있고, DP 전개를 위해선 맨 앞에 빈 값 ''이 존재해야 하기 때문이에요.

그리고, 행과 열을 순차적으로 돌면서 아래와 같은 조건으로 전개 했어요.

i = 행s, j = 열p
1. p[j] == [a-zA-Z] || p[j] == ? $\to$ dp[i][j] = dp[i-1][j-1]
2. p[j] == * $\to$ dp[i][j] = dp[i-1][j] || dp[i][j-1]

답은 나올거에요, 분명. 하지만 왜 그런지는 예제를 통해서 설명해 볼게요.

앞서 말씀드린대로 s와 p로 배열을 구성했어요. 물론 앞에 빈 값을 의미하게 +1을 해주었어요.

처음엔 dp[0][0]은 서로 빈 값끼리 일치하니까 true 처리를 해줘요. 그리고 나머지를 비교하면 다 틀리니까 false를 처리해 줘요.

그 다음에 a로 넘어가면, 빈 값 위치는 false지만, dp[1][1]에서 값이 일치해요. 이땐 dp[i-1][j-1] 값, true를 넣어줘야해요.

여기서 보면 알 수 있듯이 dp[i-1][j-1]의 의미는 이전에 매칭이 정상적으로 이뤄졌는지를 의미해요. 이전에 빈 값끼리의 일치한 값, 즉 과거의 상태를 기반으로 지금 현재 상태가 매칭이 이뤄졌는지를 초기화하는 것이에요. ?의 경우엔 어떤 문자열이 하나라도 들어 있다면 일치 상태가 되므로 과거 값을 기반으로 false가 되는 것이죠.

그 다음에 s의 c와 p의 *에서 상태가 바껴요. 2번 조건에선 dp[i][j] = dp[i-1][j] || dp[i][j-1]라는 로직이 여기서 전개되었어요.

왜 이렇게 전개를 했냐면, dp[i-1][j]는 'abc'와 'ab?`를 비교한 결과, dp[i][j-1]는 'ab'와 'ab?'를 비교한 결과에요. *가 나타나면 과거의 두 결과 중 하나라도 매칭이 되었다면 그 매칭된 결과를 기반으로 초기화를 수행해주는 거에요. *는 문자가 없어도 매칭이 된다고 처리되니까 true가 초기화 된거에요.

그렇게, 모든 전개를 마치고 나면 배열의 가장 마지막 원소에 답이 도출되요. 그리고 사전에 연속된 *를 제거해주면 좀 더 빨라져요. 불필요한 접근을 최소화하는 거에요.

답안

class Solution {
    public boolean isMatch(String s, String p) {
        char[] str = s.toCharArray();
        char[] pattern = p.toCharArray();

        // 중복된 *는 제거에요!
        boolean isFirst = true;
        int patternIndex = 0;
        for(int i = 0; i < pattern.length; ++i){
            if (pattern[i] == '*') {
                if(isFirst){
                    pattern[patternIndex++] = pattern[i];
                    isFirst = false;
                }
            } else{
                pattern[patternIndex++] = pattern[i];
                isFirst = true;
            }
        }

        boolean[][] dp = new boolean[str.length + 1][patternIndex + 1];
        if(patternIndex > 0 && pattern[0] == '*'){
            dp[0][1] = true;
        }
        dp[0][0] = true;

        for(int i = 1; i < dp.length; ++i){
            for(int j = 1; j < dp[i].length; ++j){
                if(pattern[j - 1] == '?' || pattern[j - 1] == str[i - 1]){
                    dp[i][j] = dp[i - 1][j - 1];
                } else if(pattern[j - 1] == '*'){
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
        return dp[str.length][patternIndex];
    }
}

참고

인도형의 강의