No10-Regular Expression Matching

2019-11-08 00:56:12

字体：大中小

来源：转载

供稿：网友

PRoblem descriptionAnalyseMethod最开始想出来的但是不能解决问题的算法

Problem description

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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("aab", "c*a*b") → true

Analyse

Method

尝试过使用最常规的方法解决。首先P字符串遇到第一个字符是的时候返回false不匹配，这是一种错误的语法。然后需要重点考虑的是遇到字符s字符串中跳过字符的问题。一般采用贪婪的跳过策略，因为本身就是一种贪婪的匹配，这种方式实现的代码能够解决一些问题。但是遇到如下的问题就会出错，比如s=abbc p=a*bbc 一旦遇到这种字符串，贪婪匹配策略失败。仔细分析代表的意义是尽可能多的匹配，所以如果在某些采用贪婪匹配失败的场合需要能够回到最初的场合重新选择匹配策略。因此这一题的解法就需要采用回朔的算法(backtracking)实现。因此实现的javaScript代码如下: