hg888皇冠手机登录

LeetCode – Regular Expression Matching And Wildcard Matching

十一月 15th, 2019  |  www.hg888.com

[LeetCode] Regular Expression Matching

 

Code

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s.equals("") && p.equals("")) return true;
        if (!s.equals("") && p.equals("")) return false;
        if (p.length() > 1 && p.charAt(1) == '*') {
            return isMatch(s, p.substring(2)) ||
                    (s.length() != 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0)) && isMatch(s.substring(1), p));
        }
        if (s.length() != 0 && p.length() != 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0)))
            return isMatch(s.substring(1), p.substring(1));
        return false;
    }
}

Regular Expression Matching

‘.’ Matches any single character.
‘ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char
s, const char p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a
“) → true
isMatch(“aa”, “.“) → true
isMatch(“ab”, “.
“) → true
isMatch(“aab”, “cab”) → true

Regular Expression Matching

 

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).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

解题思路:

题意为完结正则表明式的相配。在那之中扶持.和*

分为两种情景。设当前字符串和情势的下标分别为i,j

1、若当前方式相称达成,即p[j]==’\0’,若字符串甘休,则赶回true,不然再次来到false

2、若方式的下多少个字符不是*,即p[j+1]!=’*’。这里分意况钻探。

(1) 若s[i]==p[j],递归验证i+1, j+1

(2) 若p[i]==’.’且s[i]!=’\0’,递归验证i+1, j+1

(3) 否则,返回false

3、若形式的下二个字符是*,即p[j+1]==’*’,则反复通过递归回溯i+k,j+2(k从0增龙潜月len(s)-i,j+2意味着通过当前字符和*)。

代码如下:

 

class Solution {
public:
    bool isMatch(string s, string p) {
        return matchHelper(s, p, 0, 0);
    }

    bool matchHelper(string& s, string& p, int i, int j){
        if(p[j]=='\0'){
            return s[i]=='\0';
        }

        if( p[j + 1] != '*'){
            return ((s[i] == p[j]) || (p[j] == '.' && s[i]!='\0')) && matchHelper(s, p, i + 1, j + 1);
        }

        while((s[i] == p[j]) || (p[j] == '.' && s[i]!='\0')){
            if(matchHelper(s, p, i, j+2)) return true;
            i++;
        }
        return matchHelper(s, p, i, j+2);
    }
};

 

] Regular Expression Matching Regular
Expression Matching Implement regular expression matching with support
for . and * . . Matches any single character.* Matches zero
or…

Wildcard Matching

Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a*”) → true
isMatch(“aa”, “.*”) → true
isMatch(“ab”, “.*”) → true
isMatch(“aab”, “c*a*b”) → true

‘?’ Matches any single character.
‘ Matches any sequence of characters (including the empty
sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char
s, const char p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “
“) → true
isMatch(“aa”, “a“) → true
isMatch(“ab”, “?
“) → true
isMatch(“aab”, “cab”) → false

Regular Expression Matching

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

LeetCode题目:44. Wildcard
Matching
Implement wildcard pattern matching with support for ‘?’ and ‘*’.

Link

Regular Expression Matching –
LeetCode

Implement regular expression matching with support for ‘.’ and ‘*’.

class Solution {

    // 迭代算法
    public boolean isMatch(String text, String pattern) {

        // match[i][j] 表示 text[i + 1, i + 2....] 和 pattern[j + 1, j + 2....] 是否match
        boolean[][] match = new boolean[text.length() + 1][pattern.length() + 1];

        match[text.length()][pattern.length()] = true;

        for (int i = text.length(); i >= 0; i--) {
            for (int j = pattern.length() - 1; j >= 0; j--){
                boolean firstMatch = (i < text.length() && 
                                       (pattern.charAt(j) == text.charAt(i) ||
                                        pattern.charAt(j) == '.'));

                if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
                    match[i][j] = match[i][j + 2] || first_match && match[i + 1][j];
                } else {
                    match[i][j] = first_match && match[i + 1][j + 1];
                }
            }
        }
        return match[0][0];
    }

    // 递归算法
    public boolean isMatchRecursive(String text, String pattern) {
        // 都为空
        if (text.isEmpty() && pattern.isEmpty()) return true;

        // pattern为空,text不为空
        if (pattern.isEmpty()) return false;

        // 允许存在text为空,pattern不为空的情况,例如 text = "", pattern = "a*"

        // 第一个字符是否匹配
        boolean firstMatch = (!text.isEmpty() && 
                               (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

        if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
            // case1: 由于 * 的出现,之前的那个字符出现0次,比较 text 与 pattern.substring(2)
            boolean case1 = isMatch(text, pattern.substring(2));

            // case2: 由于 * 的出现,之前的那个字符出现多次,比较 text.substring(1) 与 pattern
            boolean case2 = firstMatch && isMatch(text.substring(1), pattern);

            return case1 || case2;
        } else {
            return firstMatch && isMatch(text.substring(1), pattern.substring(1));
        }
}

这几天刷LeetCode遇到关方岚则相配的编制程序题,在这里边记录下解题思路。

The function prototype should be:
bool isMatch(const char *s, const char *p)

class Solution {
    public boolean isMatch(String s, String p) {
        // Bottom-Up Variation 自底向上的DP
        boolean[][] match = new boolean[s.length() + 1][p.length() + 1];

        match[s.length()][p.length()] = true;

        for(int i = p.length() - 1; i >= 0; i--){
            if(p.charAt(i) == '*') {
                match[s.length()][i] = true;
            }
            else {
                break;
            }
        }

        for(int i = s.length() - 1; i >= 0; i--) {
            for(int j = p.length() - 1; j >= 0; j--) {
                if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
                    match[i][j] = match[i + 1][j + 1];
                }
                else if(p.charAt(j) == '*') {
                    match[i][j] = match[i + 1][j] || match[i][j + 1];
                }
                else {
                    match[i][j] = false;
                }
            }
        }

        return match[0][0];
    }
}
标签:, , , , , , , ,

Your Comments

近期评论

    功能


    网站地图xml地图