原题链接:#10 Regular Expression Matching
要求:
实现正则表达式匹配,支持'.'和'*'。
'.'匹配任意单字符。
'*'匹配任何0个或多个之前元素。
匹配应当覆盖整个输入字符串,而不仅仅是子串。
函数原型:
boolean isMatch(String /* string to check */ s, String /* patterns */ p)
例:
isMatch("aa", "a") → false
isMatch("aa", "aa") → true
isMatch("aaa", "aa") → false
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
难度:困难
分析:
仅仅是原题中给出的六个示例的话,考虑采用贪心算法,从patterns字符串的尾部向前扫,对于patterns中的每个字符,在待检测字符串中扫到其所能匹配的最长子串,扫描完毕后判断是否到达待检测字符串的头部即可。使用贪心算法实现的该函数见此。但是该函数在应对如isMatch("aaaa", "ab*a*c*a")时会遇到问题,当扫描a*时便会到达待检字符串头部,产生错误结果,因此贪心算法并不适用。
仍然从待检字符串尾部向前扫描,设0≤j<s.length(),考虑对于子串s[j..s.length()-1]能够在正则表达式p找到匹配(match[j])的条件为s[j+1...s.length()-1]匹配且s[j]也能够在pattern中找到匹配。如何判断“s[j]也能够在pattern中找到匹配”呢?需要分两种情况讨论,设i为pattern索引,第一种情况:若p[i]不为'*',则进行单字符判断,当p[i]=='.'或p[i]==s[j]时match[j]成立;第二种情况:p[i]为"*",则match[j]成立的条件为p[i-1]=='.'或p[i-1]==p[j]。另外,在这种情况下若match[j]已经被置为true,就算p[i-1]=='.'||p[i-1]==p[j]不成立也应将其值保持,因为*出现时,其之前元素可以为0个。
解决方案:
Java - 340 ms
// Dynamic Programming Solution public boolean isMatch(String /* string to check */ s, String /* patterns */ p) { boolean[] match = new boolean[s.length()+1]; for(int i=0; i<match.length; i++){ match[i] = 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)=='.'||p.charAt(i-1)==s.charAt(j)); } 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 LeetCode 学习之路 记录自己完成LeetCode的代码和结果。 序号 中文名称 英文名称 通过率 难度 1 Two Sum 47.0% 简单 2 Add Two Numbers 36.0% 中等 3 Longest Substring Without ...
动态规划 longest common prefix , 简单 valid number, hard, 用有限自动机 integer to roman ,easy , 模拟 roman to integer ,easy , 模拟 count and say , easy , 模拟 Anagrams 字符串处理,map Simplify Path,...
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
leetcode正则表达式 DP-7 Problem1 Edit Distance () Problem2 Regular Expression Matching ()
10.Regular Expression Matching: 递归的方法:当前正则第二个字符不为'*',很简单,比较当前,两个指针都往右移动即可,继续这样比较。如果为空,则有两种方式,第一种是正则的指针往后移动,字符串的保持不变,另一...
动态规划,类似于求最大连续和,但这里由于是乘法,还要考虑符号问题。于是需要记录最大与最小值。 Reverse Words in a String C++实现时那个返回值是void也着实让我困惑了好久 Subsets DFS实现,竟然还WA了好几次。...
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 2 sum c myLeetCodeReport 此仓作为春招以及秋招找工作刷题的一个记录吧。 Leetcode # title solution difficulty 1 Two Sum easy 2 Add Two Numbers medium 3 Longest Substring Without Repeating ...
lru cache leetcode Leetcode Solution 1. Two Sum ...动态规划,列出转换方程即可,注意初值 记T[i][j] = 是否S[0:i]和P[0:j]匹配 再分类讨论,其中pattern *分为0, 1, more三种类型 0: i不变, j+1
10.Regular Expression Matching 11.Container With Most Water 12.Integer to Roman 13.Roman to Integer 14.Longest Common Prefix (Trie树待完成) 15.3Sum 16.3Sum Closest 17.Letter Combinations of a Phone ...
leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。 ** Leetcode 题目列表 005 Longest Palindromic Substring 006 ZigZag Conversion 007 Reverse Integer 008 ...
leetcode 答案 leet code 这是我的leetcode答案,语言主要是用python。很多算法不是最优,甚至很槽糕,有空就会优化 目前完成了: Two Sum Add Two Numbers Longest Substring Without Repeating Characters Median ...
leetcode 跳跃 LeetCode Solved by Python easy/middle/hard:15/36/5 1. Two Sum 两数之和 2. Add Two Numbers 两数相加 3. Longest Substring Without Repeating Characters 无重复字符的最长子串 4. Median of ...
Leetcode_coding_Everyday 我每天都会解决有关leetcode的问题!... regular_expression_matching 水平扫描 #2021/04/03 int_to_Roman #2021/04/04 longest_common_prefix container_with_most_water
lru cache leetcode leetcode leetcode solutions in C++ 微信公众号:曲奇泡芙 (互联网&车联网技术) ..../0010-regular-expression-matching.cpp ./0011-container-with-most-water.cpp ./0012-int
这里使用menecher方法,就是动态规划,首先在原先的字符串之间插入'#, 这样可以统一处理奇数串和偶数串, 使用两个变量纪录状态, far_pos表示最长回文字符串的最大边界距离,ci表示最长回文字符串的中心位置, 状态...
[10_regular-expression-matching.cpp] [100_same-tree.cpp] [1001_sorted-merge-lcci.cpp] [101_对称树.cpp] [102_binary-tree-level-order-traversal.cpp] [103_binary-tree-zigzag-level-order-traversal.cpp] ...
leetcode添加元素使和等于 经验教训 一定要吧功能尽量细化为函数,这样一者做题思路比较清晰,二者可以在某些情况下直接return值。 如果输入的形式是一个序列,则可以想想:分治、动规、贪婪,一般不建议搜索,因为...
(/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-...
LeetCode判断字符串是否循环 LeetCode Javascript Solutions to problems on LintCode # question difficulty 1 Two Sum Easy 2 Add Two Numbers Medium 3 Longest Substring Without Repeating Characters Medium 4...