[LeetCode # 44] Wildcard Matching

주어진 문자열 패턴 p 가 문자열 s 를 커버할 수 있는 지 체크하는 문제

문자열 s 와 패턴 p 의 길이는 각각 0 ~ 2000 으로 제한되고 s 는 영어 소문자로만 이루어진 문자열, p 는 영어 소문자와 '?' '*' 로만 이루어진 문자열 패턴으로 주어진다. '?' 은 어떤 문자든 하나만 매치가 가능하고, '*' 은 어떤 문자열의 연속이든 매치될 수 있다. (빈 문자열도 가능)

 

문제의 풀이 방식은 다음과 같다. s 와 p 의 인덱스를 각각 저장하고 현재 인덱스의 문자열과 패턴을 비교해 어떤 인덱스를 증가시킬 것인지 선택한다.

 

우선, s 의 현재 문자를 sc, p 의 현재 문자를 pc 라 하면 sc 와 pc 가 같거나 pc 가 '?' 일 때는 두 인덱스를 모두 증가시킨다.

그렇지 않고, pc 가 '*' 일 경우, '*' 문자가 등장한 패턴의 위치와 문자열의 위치를 저장한다. 이후 문자열과 패턴이 일치하지 않을 때 다시 돌아가서 확인하기 위함이다.

마지막으로, 위의 조건에 부합하지 않은 경우는 기존에 저장된 '*' 문자가 있는 지를 확인한 후, 해당 위치로 돌아가서 문자열 인덱스를 하나 증가시킨다. '*' 문자는 어떤 문자열과도 매칭이 가능하기 때문에 다시 해당 위치부터 매칭 조건을 확인하도록 한다.

문자열 탐색이 완료된 후 패턴의 인덱스가 패턴의 길이와 일치하지 않는 경우는, 남은 패턴의 문자가 모두 '*' 문자인 지 확인한 후 그렇지 않으면 매칭이 되지 않는다 판단한다. 또한 어떤 조건에도 부합하지 않는 경우에도, 매칭이 불가능한 문자열과 패턴으로 판단한다.

 

이와 같은 풀이로 작성한 코드는 다음과 같다.

 

class Solution {
public:
    bool isMatch(string s, string p) {
        int si = 0, pi = 0;
        int star = -1, stari = 0;
        while (si < s.length()) {
            if (p[pi] == '?' || s[si] == p[pi]) {
                si++;
                pi++;
                continue;
            }

            if (p[pi] == '*') {
                star = pi++;
                stari = si;
                continue;
            }

            if (star != -1) {
                pi = star + 1;
                si = ++stari;
                continue;
            }

            return false;
        }

        while (pi < p.length()) {
            if (p[pi] != '*')
                return false;
            pi++;
        }

        return true;
    }
};

 

이 문제는 아래의 블로그 포스팅을 참고해 문제 풀이를 작성했다.

 

Reference : http://yucoding.blogspot.com/2013/02/leetcode-question-123-wildcard-matching.html