Regular Expression Matching
https://leetcode.com/problems/regular-expression-matching/description/
Regular Expression Matching - LeetCode
Can you solve this real interview question? Regular Expression Matching - Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: * '.' Matches any single character. * '*' Matches zero or more of
leetcode.com
주어진 문자열이 패턴에 맞는 문자열인지 확인하는 문제이다. 주어지는 패턴은 '.' 일 경우 같은 모든 문자에 대칭 되고, '*' 일 경우 앞 글자 하나와 함께 묶여 해당 문자가 여러 개 가능하다는 뜻이다. DP로 해결이 가능하고 이전에 풀었던 다른 문제들의 경험 덕분에 풀 수 있었다. 아래의 두 문제와 점화식을 만들어 가는 방식이 비슷하다.
https://leetcode.com/problems/edit-distance/description/
https://ygs3004.tistory.com/97
Edit Distance
https://leetcode.com/problems/edit-distance/ Edit Distance - LeetCodeCan you solve this real interview question? Edit Distance - Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the fol
blog.honey-sleep.co.kr
https://leetcode.com/problems/longest-common-subsequence/description/
https://ygs3004.tistory.com/78
Longest Common Subsequence
https://leetcode.com/problems/longest-common-subsequence/description/ Longest Common Subsequence - LeetCodeCan you solve this real interview question? Longest Common Subsequence - Given two strings text1 and text2, return the length of their longest common
blog.honey-sleep.co.kr
각 문자의 부분 문자열을 기반으로 DP 배열의 초기화와 점화식을 세워줄 수 있다. 특정 문자열 s의 인덱스 j 와 패턴 p의 문자열 i일 때를 생각해 보자. "." 또는 각 문자가 해당 인덱스에서 같을 경우 dp 배열의 true,false 값은 (i - 1)(j - 1)의 값과 같다. 왜냐하면 각 글자가 추가 되기 전에 같았다면 새로운 글자가 똑같이 생긴 경우이기 때문이다. 그리고 각 글자가 다를 경우 당연히 false가 된다.
별이 있는 패턴의 경우 해당 패턴의 i - 1 일 때의 값이 참인 경우에 참이 된다. 패턴의 새로운 문자열과 별개로 참이기 때문이다. 또한 j - 1 이 참일 경우 별문자의 문자값과 j의 문자값이 같을 경우 참이 된다. 그 이전까지의 문자가 패턴에 부합할 때 별 문자의 문자 새로 생겼다고 판단할 수 있기 때문이다. 아래에 임의의 값을 가지고 True, False 값을 찾아가는 배열을 만든 경우이다. i인 row가 늘어나는 경우를 패턴, j인 col이 늘어나는 경우가 문자열을 나타낸다.
| "" | a | b | b | e | |
| "" | T | F | F | F | F |
| a | F | T | F | F | F |
| *b | F | T | T | T | F |
| e | F | F | F | T | T |
| g | F | F | F | F | F |
확인해 보아야 하는 관계는 각 글자가 같을 때 (i - 1). (j - 1)의 값을 참조 해야 한다는 것, 별패턴일 경우엔 (i - 1)의 값과 문자가 같을 때 (j - 1)의 값을 참조 해야 한다는 점이다.
해당 규칙을 이용해서 최종적으로 통과한 코드는 아래와 같다. 별표의 경우 문자 + 별로 두 글자의 인덱스를 차지하므로 대문자로 치환하여 비교문을 작성했다.
public class Solution {
public boolean isMatch(String s, String p) {
final String dotStar = String.valueOf((char)('a' - 1));
// * + 문자를 대문자로, . 일 경우 dotStar로 치환(char < 'a'로 부등호로 비교하기 위하여)
while(p.indexOf("*") > - 1){
int starIdx = p.indexOf("*");
String starChar = String.valueOf(p.charAt(starIdx - 1)).toUpperCase();
starChar = starChar.equals(".") ? dotStar : starChar;
p = p.substring(0, starIdx - 1) + starChar + p.substring(starIdx + 1);
}
boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
dp[0][0] = true;
for(int i = 1; i < dp.length; i++){
dp[i][0] = (p.charAt(i - 1) != '.') && (p.charAt(i - 1) < 'a') && dp[i - 1][0];
}
for(int i = 1; i < dp.length; i++){
char char1 = p.charAt(i - 1);
for(int j = 1; j < dp[0].length; j++){
char char2 = s.charAt(j - 1);
if(char1 == '.' || (char1 == char2)){
dp[i][j] = dp[i - 1][j - 1];
}else if(char1 < 'a'){
dp[i][j] = dp[i - 1][j] || (dp[i][j - 1]
&& (char1 == (char)('a' - 1) // dotStart일 경우
|| ((char1 + ('a' - 'A')) == char2))); // 대문자일 경우
}else{
dp[i][j] = false;
}
}
}
return dp[p.length()][s.length()];
}
}