[LeetCode] Wildcard Matching

문제

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).

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

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa" p = "*" Output: true Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb" p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input: s = "adceb" p = "*a*b" Output: true Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input: s = "acdcb" p = "a*c?b" Output: false

 

Approach

https://noname122.tistory.com/23 이것과 비슷하면서도 다른 문제

http://yucoding.blogspot.com/2013/02/leetcode-question-123-wildcard-matching.html 여기를 참고해서 풀었다.

'?'는 어떤 한 문자에도 대응될 수 있고 '*'는 어떤 길이의 어떤 문자에도 대응될 수 있다.

따라서 '*'를 어떻게 처리하느냐가 관건인 문제.

문자열과 패턴을 매치할때는 4가지 경우가 있다.

1. 문자열과 패턴의 문자가 일치, 혹은 패턴의 문자가 '?' -> 문자열과 패턴 모두 다음 문자로

2. 패턴의 문자가 '*' -> 현재까지 읽은 문자열의 index와 패턴에서 '*'의 index 저장하고 패턴의 index 1 증가

3. 문자열과 패턴의 문자가 불일치하나 이전에 패턴에서 '*'를 읽은 적이 있음 -> 불일치 하는 것을 '*'로 퉁치기 위해 패턴의 문자는 '*'의 다음 문자로, 문자열의 문자는 '*'가 나왔을 때 기록해둔 문자의 다음 문자로 한다.

4. 1,2,3번이 모두 안되면 false

마지막으로 문자열을 다 읽었으면 패턴의 남은 부분도 모두 읽고 최종 결과를 return 한다. (패턴의 남은 부분을 문자열과 비교함)

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_WildcardMatching.cpp

chi3236/algorithm