【010-Regular Expresssion Matching(正則表達式匹配)】


【LeetCode-面试算法经典-Java实现】【全部题目文件夹索引】

原题

  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”) → false

  isMatch(“aa”,”aa”) → true

  isMatch(“aaa”,”aa”) → false

  isMatch(“aa”, “a*”) → true

  isMatch(“aa”, “.*”) → true

  isMatch(“ab”, “.*”) → true

  isMatch(“aab”, “c*a*b”) → true

题目大意

  实现一个正則表達式匹配算法。.匹配随意一个字符。*匹配0个或者多个前导字符

解题思路

  使用标记匹配算法法。从后向前进行匹配。

代码实现

import java.util.Arrays;

public class Solution {
/**
* 010-Regular Expresssion Matching(正則表達式匹配)
*
* @param s 匹配串
* @param p 模式串
* @return 匹配结果,true匹配,false不匹配
*/
public boolean isMatch(String s, String p) {
// 标记数数组
boolean[] match = new boolean[s.length() + 1];
// 初始化
Arrays.fill(match, false);
// 假定最后的结果是匹配的
match[s.length()] = true; // 对模式串从后向前进行处理
for (int i = p.length() - 1; i >= 0; i--) { // 假设当前是*
if (p.charAt(i) == '*') { // 匹配串从最后一个開始处理
for (int j = s.length() - 1; j >= 0; j--) {
match[j] = match[j] || match[j + 1] && (p.charAt(i - 1) == '.' || s.charAt(j) == p.charAt(i - 1));
}
i--;
}
// 假设不是*
else {
for (int j = 0; j < s.length(); j++) {
match[j] = match[j + 1] && (p.charAt(i) == '.' || p.charAt(i) == s.charAt(j));
} match[s.length()] = false;
}
}
return match[0];
}
}

评測结果

  点击图片,鼠标不释放。拖动一段位置。释放后在新的窗体中查看完整图片。



【LeetCode-面试算法经典-Java实现】【010-Regular Expresssion Matching(正則表達式匹配)】-LMLPHP

特别说明

欢迎转载,转载请注明出处【http://blog.csdn.net/derrantcm/article/details/46951847

05-18 00:59
查看更多