题目:
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次或者多次。注意,这个*不是代表任意0个到多个字符。而是值得前面的字符出现次数。表示刚开始做的时候想成了编译的NFA。
一开始看这个题目确实有些蒙住了。上午上课期间想了想,没有找到好的办法解决。于是乎搜了一下大神的代码,学习了一下思想。并自己尝试写了出来。
代码:
public static boolean isMatch(String s, String p) {
return Bf(s, p, 0, 0);
}
public static boolean Bf(String s ,String p , int i , int j)//brute force算法
{
if(j == p.length())//如果一个到了结尾, 判断另一个是否结束,结束则T,否则F
return i == s.length();
if(j == p.length()-1|| //P串到结尾
p.charAt(j+1)!='*')//p下一个不是*
{
if(i == s.length()|| //S串已经走完
s.charAt(i)!=p.charAt(j)&&p.charAt(j)!='.' )
return false;
return Bf(s, p, i+1, j+1);//匹配成功,则继续下一个
}
for(;i<s.length()&&(p.charAt(j)=='.'||p.charAt(j)==s.charAt(i));i++)
{
if(Bf(s, p, i, j+2))//因为此时p.charAt(j+1) 为*,此时应该跳过当前和下一个*去匹配下一个字符,如果下一个字符之后都匹配,则成功。
//否则 i++,知道把*代表的字符全部都匹配出来后在继续。
return true;
}
return Bf(s, p, i, j+2);
}
采用的算法是brute force算法,模式匹配算法的一种。
Brute-Force算法:
也称简单匹配算法,其基本思路是:从目标串s=”s0s1…sn-1”的第一个字符开始和模式串t=”t0t1…tm-1”中的第一个字符比较,若相等,则继续逐个比较后续字符,否则,从目标串s的第2个字符开始重新与模式串t的第一个字符进行比较,依次类推,若从目标串s的第i个字符开始,每个字符依次和模式串t中的对应字符相等,则匹配成功,该算法返回i;否则匹配失败,返回-1。
犹记得大二数据结构讲了一个KMP的算法。现在怎么写完全想不起来了。等会复习之。
刚才看了下这道题的标签,要用动态规划。表示动态规划没有学习过。等会学习之~
分享到:
相关推荐
LeetCode 44. Wildcard Matching ...在 LeetCode 上看到第二个有趣的问题,是关于字符串匹配的,在接触过正则表达式后就一直想着自己实现一个实用版的正则工具,像 editplus 那样,不用做得功能齐全,实用就好。
c语言 c语言_c语言编程基础之leetcode题解第10题正则表达式匹配
c++ c++_c++编程基础之leetcode题解第10题正则表达式匹配
示例 3:输入:解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。示例 4:输入:解释: 因为 '*' 表示零个或多个,这里 'c' 为 0
c# c#_Leetcode面试题解之第10题正则表达式匹配
LeetCode问题10要求解决的是"正则表达式匹配"问题,具体来说是实现一个函数来判断一个字符串是否与一个给定的模式匹配,这里的模式可以包含.和*字符,其中.匹配任意单个字符,*表示它前面的字符可以出现任意次(包括...
leetcode 跳跃 LeetCode Solved by Python easy/middle/hard:15/36/5 ...正则表达式匹配 11. Container With Most Water 盛最多水的容器 12. Integer to Roman 整数转罗马数字 13. Roman to Integer 罗马数字转
c++ c++_c++编程基础之leetcode题解第44题通配符匹配
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。 ‘.’ 匹配任意单个字符 ‘*’ 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s的,而不是...
正则LeetCodeInC leetcode.com 中的 C 语言 目录 #1 两个总和 leetcode.com 中的链接: 问题描述: 给定一个整数数组,返回两个数字的索引,使它们相加为特定目标。 您可以假设每个输入都只有一个解决方案,并且您不...
leetcode正则表达式 DP-7 Problem1 Edit Distance () Problem2 Regular Expression Matching ()
示例 4:输入:解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".示例 5:输入:Related Topics贪心算法字符
leetcode中国 我自己的leetcode刷题记录 ###[20150920] Valid Palindrome Implement strStr() String to Integer (atoi) addBinary longestPalindrome maximal rectangle :dp问题,较难 largestRectangleArea 求直方...
正则#Introducion 这个存储库将保存我为解决 leetcode 问题而编写的代码。 同时,我想告诉自己提高能力,就像我每天要推送一些代码来解决leetcode上的问题一样。 好了,走吧! #第一天时间:2017年1月5日 问题: 1....
正则表达式匹配(难) leetcode 12 - 整数到罗马(我不知道罗马) leetcode 13 - 罗马到整数(我不知道罗马) leetcode 23 - 合并 k 个排序列表(难) leetcode 25 - k-Group 中的反向节点(硬) leetcode 30 - 连接...
leetcode题库 Leetcode_Java Leetcode题解_Java 使用Java语言编写的Leetcode题解(中文) 暂停/延缓更新声明 由于将主要精力转移到科研工作,因此此仓库暂停/延缓更新。
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
密码leetcode的源代码存储库概述解决提供的算法问题。 项目中使用的约定为: 分支:leetcode问题URL的最后路径包:将leetcode问题url的最后路径转换为蛇形类:Solution.java 测试:SolutionTest.java 前任) url ...
分割数组求最大差值leetcode LeetCode 学习之路 记录自己完成LeetCode的代码和结果。 序号 中文名称 英文名称 通过率 难度 1 Two Sum 47.0% 简单 2 Add Two Numbers 36.0% 中等 3 Longest Substring Without ...
leetcode-10月