算法016

描述

正则表达式匹配问题

请实现一个函数用来匹配包括 ‘.’ 和 ‘*’ 的正则表达式。模式中的字符 ‘.’ 表示任意一个字符，而 ‘*’ 表示它前面的字符可以出现任意次（包含 0 次）。

. 一个任意字符

* 表示*前字符出现（0-？）字符

例子

aaa 以下两模式串均可匹配

ab*ac*a  a.a
	

思路

采用两个下标，分别记录目标串与模式串。 循环模式串，若为.，则下标加1； 若为模式串与目标串字符相同，则下标加1，否则看模式串下一个字符算法为*；

代码

public class Demo016 {
    public static void main(String[] args) {
        String string = "aaa";
        String pattern = "ab*a";

        int index = 0;
        int i = 0;
        boolean result = true;

        for (i = 0; i < pattern.length(); i++) {
            if (index >= string.length()) {
                result = false;
                break;
            }
            if (pattern.charAt(i) == '.') {
                index++;
                continue;
            }
            if(pattern.charAt(i) == string.charAt(index)) {
                index++;
            } else if(pattern.charAt(i+1) != '*') {
                result = false;
                break;
            } else if (pattern.charAt(i+1) == '*') {
                i++;
            }
        }
        if(index != string.length() || i != pattern.length()) {
            result = false;
        }
        System.out.println(result);
    }
}