编程题：正则表达式匹配

末蓝、 2022-05-21 05:20 199阅读 0赞

## 题目描述 ##

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

#### 思路： ####

#### 分析；常规中，如果是普通的两个字符串，那很简单，我们直接进行对比就可以了，这里又是要求匹配是指字符串的所有字符匹配整个模式，所以只要直接挨个比较就可以了，如果都相等则返回true；否则返回false；可是这个题目来了一个'.'和'\*'两个比较烦人的东西，它改变了游戏的规则。把游戏变的复杂多变。   首先要明确'.'确定了字符的个数为1，并且为任意；'\*'可以确定它前面的字符的个数包括0次；   第一种情况：当模式的第二个字符不是'\*'的时候，如果字符串的第一个字符和模式串的第一个字符相等，则都向后移动一个，匹配剩下的字符串和模式串。如果不等则直接返回false；   第二种情况：当模式的第二个字符是'\*'的时候，这时候就稍复杂点儿，因为这时候存在不同的几种匹配方式：以字符串"aaa"与模式"ab\*ac\*a"匹配为例：   1、如果模式串中的字符和字符串中的字符不等如(a)，且模式串的第二个字符为'\*'。    ####

选择只有一种：在模式串上向后移动两个字符,忽略掉b和\*，因为'\*'可以匹配0个字符

2、如果模式串中的字符和字符串中的字符相等如(b)，或者模式串中为'.'如(c)，并且模式串的第二个字符为'\*'。其实(b)和(c)是一样的。这时候选择有三种情况：  
（1）可以选择在模式串上向后移动两个字符,忽略掉b和\*，因为'\*'可以匹配0个字符，字符串str保持不变；  
（2）可以选择越过'\*'，'\*'前的a当作有效的字符，且数量为1，str++；  
（3）可以选择模式串pattern不变，因为‘\*’前的a可以任意数量的，并且和字符串str相等，只需要str++即可；

#### 代码： ####

package com.example.demo;
    
    import java.util.Scanner;
    
    /**
     * Created by ASUS on 2018/6/30
     *
     * @Authod Grey Wolf
     */
    public class Practice {
    
        public static void main(String[] args) {
            Practice p=new Practice();
            p.sys();
        }
    
        private void sys() {
            Scanner sc=new Scanner(System.in);
            while(sc.hasNextLine()) {
                char[] str = sc.nextLine().toCharArray();
                char[] pattern = sc.nextLine().toCharArray();
                boolean flag = getRes(str, pattern);
                System.out.println("flag-->" + flag);
            }
        }
        private boolean getRes(char[]str,char[]pattern) {
            if (str==null||pattern==null){
                return false;
            }
            int strIndex=0;
            int patternIndex=0;
            return getRess(str,strIndex,pattern,patternIndex);
        }
    
        private boolean getRess(char[] str, int strIndex, char[] pattern, int patternIndex) {
            //有效性检验，str到尾，pattern到尾，匹配成功
            if (strIndex==str.length&&patternIndex==pattern.length){
                return true;
            }
            //pattern先到尾，匹配失败
            if (strIndex!=str.length&&patternIndex==pattern.length){
                return false;
            }
            //模式第二个是*，且字符串第一个跟模式第一个匹配，分3种匹配模式，如不匹配，模式后移3位
            if (patternIndex+1<pattern.length&&pattern[patternIndex+1]=='*'){
                if (strIndex!=str.length&&pattern[patternIndex]==str[strIndex]||
                        (pattern[patternIndex]=='.'&&strIndex!=str.length)){
                    return getRess(str,strIndex,pattern,patternIndex+2)
                            ||getRess(str,strIndex+1,pattern,patternIndex+2)
                            ||getRess(str,strIndex+1,pattern,patternIndex);
                }else {
                    return getRess(str,strIndex,pattern,patternIndex+2);
                }
    
            }
            if ((strIndex!=str.length&&pattern[patternIndex]==str[strIndex])
                    ||(pattern[patternIndex]=='.'&&strIndex!=str.length)){
                return getRess(str,strIndex+1,pattern,patternIndex+1);
            }
            return false;
        }
    
    }

#### 效果： ####

aaa  
a.a  
flag-->true  
aaa  
aa.a  
flag-->false

我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。