简化的正则表达式匹配-JAVA，正则表达式-java,这是最近接触到的某公司的

简化的正则表达式匹配-JAVA，正则表达式-java,这是最近接触到的某公司的

这是最近接触到的某公司的面试题目，感觉有点意思，就小小的研究了一番，题目的要求如下：

On an alphabet set [a-z], a simplified regular expression is much simpler thanthe normal regular expression.

It has only two meta characters: '.' and '*'.

'.' -- exact one arbitrary character match.

'*' -- zero or more arbitrary character match.

Note that it is different from the normal regular expression in that '' is onits own and does NOT act as a decorator on the leading character, I.e. in oursimplified regular expression. "" is equivalent to ".*" in regularexpression.

Write a parser which takes a pattern string and a candidate string as inputand decides to either accept or reject the candidate string based on thepattern string.

Only the full match is acceptable. The parser rejects partial matches.

You can safely assume all the characters in both input pattern string andcandidate string are valid characters, i.e. you don't need to validate theinput strings.

Your parser need to at least pass all the following test cases.

You can write the parser in any programing language you like.

Write up an analysis on the run-time complexity of your code.

package com.hanmiao.exam;import java.util.regex.Matcher;import java.util.regex.Pattern;public class Example{    public static int SIZE = 25;    public static String[] patterns = {"abc","*", "*abc", "*abc", "a*bc", "a*bc", "a*", "a*", "a*", "a*"        , "*abc*", "*****","...",".*", ".bc*", ".b*c*a", "*", "abc", "*a", "a"        , ".a*c", "a.*b", "..", "", ""};    public static String[] candidates = {"abc", "abc", "abc", "aaabbbabc", "aaabbbabc", "abc", "abc", "a", "aa", "abcdef"        , "abc", "abc", "abc", "abc","abc", "abca", "", "abcd", "abcd", ""        , "abc", "abc", "abc", "", "abc"};    public static void main(String[] args){        for(int i = 0; i < SIZE; i ++){            System.out.println("pattern=\\"" + patterns[i] + "\\"\\t candidate=\\"" + candidates[i] + "\\"\\t result=" + parser(patterns[i], candidates[i]));        }    }    public static String parser(String pattern, String candidate){        if(pattern.length() == 0){            return "reject";        }               pattern = pattern.replace("*", ".*");        Pattern p = Pattern.compile(pattern);        Matcher m = p.matcher(candidate);        return m.matches() ? "accept" : "reject";    }}//该片段来自于http://byrx.net