`
Cwind
  • 浏览: 262392 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
博客专栏
793bb7df-a2a9-312d-8cb8-b66c3af482d1
LeetCode题解
浏览量:52259
社区版块
存档分类
最新评论

LeetCode[动态规划] - #10 Regular Expression Matching

阅读更多

原题链接:#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];
    }

 简单测试程序

1
1
分享到:
评论

相关推荐

    分割数组求最大差值leetcode-Leetcode-Road:LeetCode刷题记录

    分割数组求最大差值leetcode LeetCode 学习之路 记录自己完成LeetCode的代码和结果。 序号 中文名称 英文名称 通过率 难度 1 Two Sum 47.0% 简单 2 Add Two Numbers 36.0% 中等 3 Longest Substring Without ...

    leetcode中国-leetcode:leetcode刷题

    动态规划 longest common prefix , 简单 valid number, hard, 用有限自动机 integer to roman ,easy , 模拟 roman to integer ,easy , 模拟 count and say , easy , 模拟 Anagrams 字符串处理,map Simplify Path,...

    LeetCode-in-Golang:使用 Golang 解答 LeetCode

    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:DP-7

    leetcode正则表达式 DP-7 Problem1 Edit Distance () Problem2 Regular Expression Matching ()

    leetcode怎么销号-leetcodeAns:leetcode问题的答案python

    10.Regular Expression Matching: 递归的方法:当前正则第二个字符不为'*',很简单,比较当前,两个指针都往右移动即可,继续这样比较。如果为空,则有两种方式,第一种是正则的指针往后移动,字符串的保持不变,另一...

    leetcode写题闪退-LeetCode:leetcodeOJ

    动态规划,类似于求最大连续和,但这里由于是乘法,还要考虑符号问题。于是需要记录最大与最小值。 Reverse Words in a String C++实现时那个返回值是void也着实让我困惑了好久 Subsets DFS实现,竟然还WA了好几次。...

    lrucacheleetcode-luoleet:LeetcodesolutionsbyXinhangLuoandQinghaoDai

    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/ ...

    leetcode2sumc-myLeetCodeReport:我的LeetCode报告

    leetcode 2 sum c myLeetCodeReport 此仓作为春招以及秋招找工作刷题的一个记录吧。 Leetcode # title solution difficulty 1 Two Sum easy 2 Add Two Numbers medium 3 Longest Substring Without Repeating ...

    lrucacheleetcode-leetcode-1:leetcode-1

    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

    leetcode338-LeetCode:LeetCode刷题总结

    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 ...

    leetcode530-algorithm:算法

    leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。 ** Leetcode 题目列表 005 Longest Palindromic Substring 006 ZigZag Conversion 007 Reverse Integer 008 ...

    leetcode答案-leetcode:leetcode

    leetcode 答案 leet code 这是我的leetcode答案,语言主要是用python。很多算法不是最优,甚至很槽糕,有空就会优化 目前完成了: Two Sum Add Two Numbers Longest Substring Without Repeating Characters Median ...

    leetcode跳跃-LeCode:乐科

    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_coding_Everyday 我每天都会解决有关leetcode的问题!... regular_expression_matching 水平扫描 #2021/04/03 int_to_Roman #2021/04/04 longest_common_prefix container_with_most_water

    lrucacheleetcode-leetcode:leetcodesolutionsinC++微信公众号:曲奇泡芙(互联网&智能汽车技术)

    lru cache leetcode leetcode leetcode solutions in C++ 微信公众号:曲奇泡芙 (互联网&车联网技术) ..../0010-regular-expression-matching.cpp ./0011-container-with-most-water.cpp ./0012-int

    leetcode数组下标大于间距-leetcode:leetcode刷一遍

    这里使用menecher方法,就是动态规划,首先在原先的字符串之间插入'#, 这样可以统一处理奇数串和偶数串, 使用两个变量纪录状态, far_pos表示最长回文字符串的最大边界距离,ci表示最长回文字符串的中心位置, 状态...

    lrucacheleetcode-LeetCode_Note:leetcode个人笔记

    [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添加元素使和等于-leetcode:我的leetcode解决方案

    leetcode添加元素使和等于 经验教训 一定要吧功能尽量细化为函数,这样一者做题思路比较清晰,二者可以在某些情况下直接return值。 如果输入的形式是一个序列,则可以想想:分治、动规、贪婪,一般不建议搜索,因为...

    lrucacheleetcode-LeetCode:我从LeetCode提交的一些任务

    (/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:LeetCode问题的Javascript解决方案

    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...

Global site tag (gtag.js) - Google Analytics