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
代码:
//递归从左至右依次匹配 public boolean isMatch(String s, String p) { // Note: The Solution object is instantiated only once and is reused by each test case. if(s == null||p == null) return false; return isMatch(s,p,0,0); } //递归函数isMatch(s,p,i,j):i 指示 s , j 指示p public boolean isMatch(String s,String p,int i, int j){ int slen = s.length(); int plen = p.length(); if(j>=plen){//递归结束 if(i>=slen) return true; else return false; } if(j == plen-1){//j已经指向最后一位,递归结束 if(i!=slen-1) return false; if(s.charAt(i) == p.charAt(j)||p.charAt(j) == '.') return true; return false; } char c = p.charAt(j+1); if(c != '*'){//p[j+1] !=‘ * ‘ 说明当前p[j]只能匹配一个 if(i<=slen-1&&(s.charAt(i) == p.charAt(j)||p.charAt(j) =='.')) return isMatch(s,p,i+1,j+1);//继续匹配后续字符串 else return false; }else{ //匹配0(注意可以是0个,所以i没有++)到多个p[j]或者任意字符(p[j] =='.' ) while(i<=slen-1&&(s.charAt(i) == p.charAt(j)||p.charAt(j) =='.')){ if(isMatch(s,p,i,j+2)) return true; i++; } return isMatch(s,p,i,j+2);//走到第一个不匹配的之后,继续后续过程 } }
相关推荐
Expression Matching 递归匹配 wildcard matching 动态规划 longest common prefix , 简单 valid number, hard, 用有限自动机 integer to roman ,easy , 模拟 roman to integer ,easy , 模拟 count and say , easy ,...
LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7....
分割数组求最大差值leetcode LeetCode 学习之路 记录自己完成LeetCode的代码和结果。...Expression Matching 25.3% 困难 11 Container With Most Water 59.3% 中等 12 Integer to Roman 61.8% 中等 13 Roman to In
Expression Matching 011 Container With Most Water 012 Integer to Roman 013 Roman to Integer 014 Longest Common Prefix 015 3Sum 016 3Sum Closest 017 Letter Combinations of a Phone Number 018 4Sum 020 ...
leetcode添加元素使和等于 经验教训 一定要吧功能尽量细化为函数,这样一者做题思路比较清晰,二者可以在某些情况下直接return值。 如果输入的形式是一个序列,则可以想想:分治、动规、贪婪,一般不建议搜索,因为...
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 13 Two Sum 47 14 Two Sum II Input array is sorted 49 15 Two Sum III Data structure design 51 16 3Sum 53 17 4Sum 55...
35%2☆ ☆27%3☆ ☆24%4☆ ☆ ☆21%5☆ ☆25%6☆ ☆26%7☆24%8☆ ☆13%9Palindrome Number☆35%10Regular Expression Matching☆ ☆ ☆24%:red_heart:11Container With Most Water☆ ☆36%12Integer to R
https://leetcode.com/problems/regular-expression-matching/ Regular Expression Matching 100 https://leetcode.com/problems/same-tree/ Same Tree 101 https://leetcode.com/problems/symmetric-tree/ ...
leetcode Python 001 leetcode的算法问题 这是我的解决方案,用 ...Expression Matching 011. Container With Most Water 012. Integer to Roman 013. Roman to Integer 014. Longest Common Prefix 019. R
leetcode 答案 leet code 这是我的leetcode答案,语言主要是用python。很多算法不是最优,甚至很槽糕,有空就会优化 目前完成了: Two Sum Add Two Numbers Longest ...Regular Expression Matching
leetcode 跳跃 LeetCode Solved by ...Expression Matching 正则表达式匹配 11. Container With Most Water 盛最多水的容器 12. Integer to Roman 整数转罗马数字 13. Roman to Integer 罗马数字转
lru cache leetcode Leetcode ...Expression Matching 动态规划,列出转换方程即可,注意初值 记T[i][j] = 是否S[0:i]和P[0:j]匹配 再分类讨论,其中pattern *分为0, 1, more三种类型 0: i不变, j+1
leetcode正则表达式 DP-7 Problem1 Edit Distance () Problem2 Regular Expression Matching ()
leetcode数组下标大于间距 5. Longest Palindromic Substring 这里使用menecher方法,就是动态规划,首先在原先的字符串之间插入'#, 这样可以统一处理奇数串和偶数串, 使用两个变量纪录状态, far_pos表示最长回文...
10.Regular Expression Matching: 递归的方法:当前正则第二个字符不为'*',很简单,比较当前,两个指针都往右移动即可,继续这样比较。如果为空,则有两种方式,第一种是正则的指针往后移动,字符串的保持不变,另一...
leetcode 2 sum c myLeetCodeReport 此仓作为春招以及秋招找工作刷题的一个记录吧。 Leetcode # title solution difficulty 1 Two Sum easy ...Regular Expression Matching hard 剑指Offer(66题)
LeetCode判断字符串是否循环 ...Expression Matching Difficult 13 Roman to Integer Easy 15 Medium 21 Easy 26 Remove Duplicates from Sorted Array Easy 142 Medium 191 Number of 1 Bit
LeetCode 自己刷LeetCode整理的一些题解笔记,有什么错误欢迎指出。 带:club_suit:为力扣2020.3.1开始的每日一题打卡 ...Regular-Expression-Matching C++, Python Hard 11:club_suit: Container-With-
(/problems/regular-expression-matching/) 24.1% 难253 38.9% 中15 21.6% 中277 寻找名人 (/problems/find-the-celebrity/) 35.4% 中等158 读取 N 个字符给定 Read4 II - 多次调用 (/problems/read-n-...