-
[LeetCode] Wildcard Matching알고리즘 2019. 10. 24. 22:39
문제
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
'알고리즘' 카테고리의 다른 글
[LeetCode] Group Anagrams (0) 2019.10.29 [LeetCode] Permutations (0) 2019.10.28 [LeetCode] Trapping Rain Water (0) 2019.10.23 [LeetCode] First Missing Positive (0) 2019.10.22 [LeetCode] Count and Say (0) 2019.10.22