[leetcode] 10. Regular Expression Matching

boricat·2021년 10월 14일
0

leetcode

목록 보기
2/14

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 the preceding element.
The matching should cover the entire input string (not partial).

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 preceding 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 = "cab"
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 = "misisp*."
Output: false

Constraints:

1 <= s.length <= 20
1 <= p.length <= 30
s contains only lowercase English letters.
p contains only lowercase English letters, '.', and ''.
It is guaranteed for each appearance of the character '
', there will be a previous valid character to match.

class Solution {
int[][] dp;

public boolean isMatch(String s, String p) {
if (s == null || p == null) return false;
dp = new int[s.length() + 1][p.length() + 1];
return judge(s, p) == 1 ? true : false;
}

private int judge(String s, String p) {
int m = s.length(), n = p.length();
if (n == 0) {
return m == 0 ? 1 : -1;
}
if (dp[m][n] != 0) {
return dp[m][n];
}
if (m == 0) {
dp[m][n] = p.charAt(n - 1) != '*' ? -1 : judge(s, p.substring(0, n - 2));
return dp[m][n];
}
dp[m][n] = -1;
if (s.charAt(m - 1) == p.charAt(n - 1) || p.charAt(n - 1) == '.') {
dp[m][n] = judge(s.substring(0, m - 1), p.substring(0, n - 1));
} else if (p.charAt(n - 1) == '*') {
dp[m][n] = Math.max(dp[m][n], judge(s, p.substring(0, n - 2)));
for (int i = m - 1; i >= 0 && (s.charAt(i) == p.charAt(n - 2) || p.charAt(n - 2) == '.'); --i) {
dp[m][n] = Math.max(dp[m][n], judge(s.substring(0, i), p.substring(0, n - 2)));
}
} else {
dp[m][n] = -1;
}
return dp[m][n];
}
}



key point:
1, init dp[0][0] && dp[0][j], to avoid corner cases;
2, transform function:
a, when p == '':
compare char[i-1][j-1];
if same, "char" can count as 0, 1, multiple;
Important: if multiple, dp[i+ 1][j+ 1] = dp[i][j+1];
think backwards, not forwards.


public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
if (n == 0) return m == 0;
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1; i < n; i+=2) {
if (p.charAt(i) != '*') break;
else dp[0][i + 1] = true;
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
char a = s.charAt(i), b = p.charAt(j);
if (b == '.' || a == b) dp[i + 1][j + 1] = dp[i][j];
else if (b == '*') dp[i + 1][j + 1] = dp[i + 1][j - 1]  // zero
|| ((s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.') && dp[i][j + 1]); // 1 or more;  // consider ".*"
}
}

return dp[m][n];
}
newbie

17개의 댓글

2021년 11월 26일

our platform is to give customers what they demand and what they deserve.
cheap csgo accounts

답글 달기
2021년 12월 2일

답글 달기
2021년 12월 4일

Great code, the author is handsome! It seemed to me that you have it too detailed and from this large in size, I think you can reduce it at least twice if you use pseudo-classes and identifiers, for example, I generally recommend watching a video on TikTok on how to shorten any code by almost five times and not cut it its functionality, unfortunately I don't remember the name of this video, but I do remember that it had posted by account that have about 34 thousand of followers! I am sure that the author of this video used services of https://viplikes.net/buy-tiktok-followers to quickly boost the number of followers.

답글 달기
2021년 12월 23일

VenuePro has 14 modules and it collaborates with both specialists and owners from the industry. The program is constantly being updated. https://venuepro.co

답글 달기
2021년 12월 26일

The economy of Mauritius has seen significant progress over the previous decades making it a preferred location not only for doing business, but also for relocation. Whether looking how to move and relocate to Mauritius, retire in Mauritius, or simply invest in a property and spend the winters in the sun, Mauritius offers some rare and exciting opportunities. https://tbimauritius.com/services/relocation-services

답글 달기
2022년 1월 6일

Hulexo ERP allows you to effectively streamline all your retail departments. Hulexo ERP helps companies cut down on excessive resources & costs while saving valuable time, money, and manual effort that gets wasted on managing the day-to-day business operations and activities while losing out on the opportunity to grow the business. https://www.hulexo.com

답글 달기
2022년 3월 9일

Installing a clear and visible CCTV system will protect your business by providing an obvious deterrent to prevent criminal activity on your premises. https://www.foresecuritysolutions.co.uk/video-surveillance

답글 달기
2022년 3월 9일

Installing a clear and visible CCTV system will protect your business by providing an obvious deterrent to prevent criminal activity on your premises. https://www.foresecuritysolutions.co.uk/video-surveillance

답글 달기
2022년 3월 9일

Installing a clear and visible CCTV system will protect your business by providing an obvious deterrent to prevent criminal activity on your premises. https://www.foresecuritysolutions.co.uk/video-surveillance

답글 달기
2022년 3월 9일

Installing a clear and visible CCTV system will protect your business by providing an obvious deterrent to prevent criminal activity on your premises. https://www.foresecuritysolutions.co.uk/video-surveillance

답글 달기
2022년 3월 9일

Installing a clear and visible CCTV system will protect your business by providing an obvious deterrent to prevent criminal activity on your premises. https://www.foresecuritysolutions.co.uk/video-surveillance

답글 달기
2022년 3월 9일

Installing a clear and visible CCTV system will protect your business by providing an obvious deterrent to prevent criminal activity on your premises. https://www.foresecuritysolutions.co.uk/video-surveillance

답글 달기
2022년 3월 10일

A team dedicated to push the limits of PowerPoint experience. We constantly push the boundaries of slide design, using the dynamic animations, sophisticated illustrations and the art of story-telling, raising the tool to an ever-higher level of other graphic design software. All results in bring that WOW effect and engaging your audience on a different level. https://samikayyali.com/powerpoint-presentation

답글 달기
2022년 4월 5일

Using our venue management portal you can easily create your Event & Theatre Performance Settlement with complete data management
https://venuearc.com/event-settlement/

답글 달기
2022년 5월 19일

I agree, it helps a lot in learning paper minecraft

답글 달기
2022년 5월 30일

Click https://www.saadashraf.net/ to get web design services in Dubai.

답글 달기
3일 전

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

답글 달기