[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];
    }
profile
newbie

17개의 댓글

comment-user-thumbnail
2021년 11월 26일

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

답글 달기
comment-user-thumbnail
2021년 12월 2일

On your place I would make a video for youtube about it and get many subscribers for your channel from here https://soclikes.com/buy-youtube-subscribers

답글 달기
comment-user-thumbnail
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.

답글 달기
comment-user-thumbnail
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

답글 달기
comment-user-thumbnail
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

답글 달기
comment-user-thumbnail
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

답글 달기
comment-user-thumbnail
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

답글 달기
comment-user-thumbnail
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

답글 달기
comment-user-thumbnail
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

답글 달기
comment-user-thumbnail
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

답글 달기
comment-user-thumbnail
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

답글 달기
comment-user-thumbnail
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

답글 달기
comment-user-thumbnail
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

답글 달기
comment-user-thumbnail
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/

답글 달기
comment-user-thumbnail
2022년 5월 19일

I agree, it helps a lot in learning paper minecraft

답글 달기
comment-user-thumbnail
2022년 5월 30일

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

답글 달기
comment-user-thumbnail
3일 전

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

답글 달기