Writer: Steven, Lee
Date: 12/19, Wednesday
Purpose: Solving #10 Regular Expression Matching
Level: Hard
Percentage: 24.6% have solved this problem
Time: it took me 7 hours :)
Dynamic programming * reference * => https://www.youtube.com/watch?v=vYquumk4nWw
한국어 버전은 밑에 있습니다.
* Caution * Before you read the solution that I used, you need to solve this problem by yourself
* Description *
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
scould be empty and contains only lowercase lettersa-z.pcould be empty and contains only lowercase lettersa-z, and characters like.or*.
* Example *
Example 1:
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa" p = "a*" Output: true Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab" p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input: s = "aab" p = "c*a*b" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:
Input: s = "mississippi" p = "mis*is*p*." Output: false
* What is the Idea? *
Let's solve this problem with the specific example, s = "aab" and p = "c*a*b".
1. we need to make a matrix like this.
x c * a * b
x
a
a
b
2. Then, we need to set a default value wheater it's true or not
x c * a * b
x T F T F T F
a F
a F
b F
3. Next, we need to consider two cases of this problem
First, two alphabets of given s and p are same. or the alphabet of p is '.' then it should be true if the previous two chars are same.
=>if (s[i-1] == p[j-1] or p[j-1] == '.'), then T[i][j] should be T[i-1][j-1];
Second, if p[j] is '*' then, it's a quite tricky thing. . because '*' can be multiple chars of previous char or it can be zero occurrence like this.
"a*" can be "aaaaaaaa" or "" also ".*" can be "abcdef", "aaabcde", ""
is it difficult?? right. Let's keep doing. so we have to deal with these cases
=> if( p[j] == '*' ) and if(s[i-1] == p[j-2] || p[i-1] == '.'),
then T[i][j] should be T[i-1][j] or T[i][j-2];
else then, T[i][j] should be T[i][j-2];
4. Final matrix looks like this. :)
x c * a * b
x T F T F T F
a F F F T T F
a F F F F T F
b F F F F F *T* <= this might be T[s,length()][p.length()];
so return T[s.length()][p.length()];
5. clear :)
* Check *
you can check out your answer on this site.
https://leetcode.com/problems/regular-expression-matching/
(한국어)
* 주의 * 솔루션을 읽기 전에 스스로 문제를 푸실 수 있어야 합니다.
* 지문 *
문자열 input s와 패턴 문자열인 p가 주어집니다. 이 패턴 문자열은 regular expression matching이 '.'와 '*' 함께 가능하게 되어있습니다.
'.'은 어떤 하나의 문자로 매칭이 될 수 있습니다.
'*'은 바로 이전의 문자를 없는 것으로 매칭을 할 수 있게 하며 혹은 그 문자가 여러번 나오는 것을 매칭이 될 수 있도록 합니다.
노트: s는 오직 a-z 만 들어옵니다. p는 a-z와 '.', '*'가 들어올 수 있습니다.
s와 p가 매칭이 되면 true를 반환하고 매칭이 안되면 false를 반환하세요.
* 예시 *
Example 1:
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa" p = "a*" Output: true Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab" p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input: s = "aab" p = "c*a*b" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:
Input: s = "mississippi" p = "mis*is*p*." Output: false
* 아이디어 *
이 문제를 어떤 예시로 접근하겠습니다. s는 "aab"이고 p는 "c*a*b"
1. 먼저 메트릭스를 다음과 같이 만듭니다.
x c * a * b
x
a
a
b
2. 그런 후, 다음과 같이 각 값마다 true인지 false인지 초기값을 줍니다.
x c * a * b
x T F T F T F
a F
a F
b F
3. 다음으로, 이 문제에서 두 가지 케이스를 고려해야 합니다.
첫 번째, 주어진 s와 p에서 얻은 두 개의 알파벳이 동일하다면 혹은 p에서 얻은 알파벳이 '.'고 이전의 두 개의 p와 s의 chars이 같으면 이것은 true입니다.
=>if (s[i-1] == p[j-1] or p[j-1] == '.'), then T[i][j]은 T[i-1][j-1]이 되어야 합니다.
두 번째, 만약 p[j]가 '*'이면 문제는 꽤 어렵게 됩니다. . 왜냐하면 '*'은 바로 이전의 문자가 여러번 올 수가 있고 아니면 이전의 문자가 없을 수 있습니다. 예를 들어보면, "a*"은 "aaaaaaaa" or ""가 될 수 있고 또한 ".*"은 "abcdef", "aaabcde", "" 될 수 있습니다.
꽤 어렵죠?? 맞아요. 계속 해볼까요?? 그래서 우리들은 이 모든 경우의 수를 생각해야 합니다.
=> if( p[j] == '*' ) and if(s[i-1] == p[j-2] || p[i-1] == '.'),
then T[i][j]은 T[i-1][j] or T[i][j-2]입니다.
else then, T[i][j]은 T[i][j-2]입니다.
4. 마지막 메트릭스는 다음과 같이 생겼습니다.
x c * a * b
x T F T F T F
a F F F T T F
a F F F F T F
b F F F F F *T* <= 이 부분은 아마도 T[s,length()][p.length()] 될 것입니다.
그래서 return T[s.length()][p.length()]입니다.
5. 완성
* Check *
이 사이트에서 정답의 유무를 확인하실 수 있습니다.
https://leetcode.com/problems/regular-expression-matching/
Code & 코드
You need to read the code by yourself
스스로 코드를 읽을 줄 알아야 합니다.
public class RegularExpressionMatching_10 {public static boolean isMatch(String s, String p) {boolean dp[][] = new boolean[s.length()+1][p.length()+1];char sChar, pChar;dp[0][0] = true;for(int i = 2 ; i <= p.length() ; i++) {if(p.charAt(i - 1) == '*' && dp[0][i-2]) dp[0][i] = true;}for(int i = 1 ; i <= s.length(); i++) {sChar = s.charAt(i-1);for(int j = 1 ; j <= p.length() ; j++) {pChar = p.charAt(j-1);if(sChar == pChar || pChar == '.') dp[i][j] = dp[i-1][j-1];else if(pChar == '*') {if(sChar == p.charAt(j-2) || p.charAt(j-2) == '.') dp[i][j] = dp[i-1][j] || dp[i][j-2];else dp[i][j] = dp[i][j-2];}}}return dp[s.length()][p.length()];}public static void main(String[] args) {String s = "aab";String p = "c*a*c*b";boolean result = isMatch(s, p);System.out.println(result);}}
'DataStructures & Algorithm (Practice)' 카테고리의 다른 글
| Leetcode #51 N-Queens (0) | 2018.12.27 |
|---|---|
| Leetcode #17 Letter Combinations of a Phone Number (0) | 2018.12.21 |
| Interview#1 Encode&Decode (Facebook) (0) | 2018.12.17 |
| Leetcode #5 Longest Palindromic Substring (0) | 2018.11.25 |
| Leetcode #4 Median of Two Sorted Array (0) | 2018.11.25 |
