资讯专栏INFORMATION COLUMN

10 Regular Expression Matching, 填dp table

MingjunYang / 2214人阅读

摘要:解释清楚这两个条件是如何推导的。表示维持原位置,位置的,和位置的一同消失。

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 class Solution {
    public boolean isMatch(String s, String p) {
        // s.substring[0,i] matched p.substring[0,j]
        boolean[][] matched = new boolean[s.length() + 1][p.length() + 1];
        matched[0][0] = true;
        
        for(int j=1; j
s = "ab"  p = ".*"
    . *
  T F T 
a F T T 
b F F T

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66928.html

相关文章

  • [LeetCode] 10. Regular Expression Matching

    Problem Given an input string (s) and a pattern (p), implement regular expression matching with support for . and *. . Matches any single character. * Matches zero or more of the preceding element. Th...

    mo0n1andin 评论0 收藏0
  • Wildcard Matching

    摘要:题目链接这道题还是可以用的方法,用的数组来解,空间复杂度较高。和不同,这道题的符号和前面的没有关系,不需要一起考虑。最坏的情况下,间隔出现且每个都要匹配很多字符,设一个平均匹配里面个字符,。其中,是的长度,是的长度。 Wildcard Matching 题目链接:https://leetcode.com/problems...这道题还是可以用Regular Expression Mat...

    galaxy_robot 评论0 收藏0
  • [Leetcode] Regular Expression Matching 正则表达式匹配

    摘要:为的条件是为,且第个字符也能被成功匹配。而从后往前匹配则不会影响该星号后面星号所匹配的部分,因为已经匹配的部分我们会直接跳过。这样才能防止最后字母没有匹配上,而前面的部分反而把的结尾给匹配了。 Regular Expression Matching Implement regular expression matching with support for . and*. . Mat...

    Vixb 评论0 收藏0
  • Leetcode 10 Regular Expression Matching 简单正则匹配

    摘要:难度这道题要求我们实现简单的正则表达式的匹配只要求普通字符的匹配了解正则的同学都清楚代表任意单个字符代表个或多个前面的字符比如可以匹配到空字符串也可以匹配等等题目还要求我们判定正则是否匹配给定的字符串要判定整个字符串而不是其中一部分匹配就算 Implement regular expression matching with support for . and *. . Matche...

    OnlyLing 评论0 收藏0
  • 一句指令,得到好看的目录树!

    摘要:想要轻松获取目录树字符串吗现在一句话就可以搞定 想要轻松获取目录树字符串吗?现在一句话就可以搞定 showImg(https://segmentfault.com/img/bVIvY2?w=417&h=747); moyu/ ├── Applications/ ├── consolas/ ├── Desktop/ ├── Documents/ ├── Downloads/ ├── in...

    junnplus 评论0 收藏0

发表评论

0条评论

MingjunYang

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<