剑指Offer: 正则表达式匹配

古城微笑少年丶 2023-07-20 10:32 18阅读 0赞

##### 1. 题目描述 #####

请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab\*a"均不匹配

原题传送门：[link][].

##### 2. 提取关键词 #####

字符串

##### 3. 思路 #####

*  暂无

##### 4. 代码（Java） #####

public class Solution {
    public boolean match(char[] str, char[] pattern)
        {
            return matchTwo(str,0,str.length,pattern,0,pattern.length);
             
        }
    private boolean matchTwo(char[] str, int i, int length1, char[] pattern,
                int j, int length2) {
            if(i==length1&&j==length2) {
                return true;
            }
            if(i==length1&&j!=length2) {
                while(j!=length2){
                    if(pattern[j]!='*'&&(j+1>=length2||pattern[j+1]!='*')){
                        return false;
                    }
                    j++;
                }
                return true;
            }
        if(i!=length1&&j==length2) {
                return false;
            }
            if(j+1==length2){
                if(str[i]==pattern[j]||pattern[j]=='.')
                    return matchTwo(str, i+1, length1, pattern, j+1, length2);
                else {
                    return false;
                }
            }
            if((str[i]==pattern[j]||pattern[j]=='.')&&pattern[j+1]!='*')
                return matchTwo(str, i+1, length1, pattern, j+1, length2);
            if((str[i]==pattern[j]||pattern[j]=='.')&&pattern[j+1]=='*')
                return matchTwo(str, i, length1, pattern, j+2, length2)||matchTwo(str, i+1, length1, pattern, j, length2);
            if(pattern[j+1]=='*')
                return matchTwo(str, i, length1, pattern, j+2, length2);
            return false;
        }
    }

##### 5.复杂度 #####

*  暂无

##### 6. 知识积累 #####

*  暂无

[link]: https://www.nowcoder.com/practice/45327ae22b7b413ea21df13ee7d6429c?tpId=13&tqId=11205&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking