LintCode 192. Wildcard Matching (Hard)

LeetCode 44. Wildcard Matching (Hard)

The second time, I was abused by this question . It's just kneeling in one place , It's about mustFail The place of .

When *p && !*s When , explain s It's been used up , p It's not exhausted yet , In this case, exit all recursive returns directly false, because s There's no match p, that s+1, s+2... It's even more impossible to match strings p.

class Solution {
private:
bool mustFail = false;
public:
bool isMatch(const char *s, const char *p) {
if (!s || !p) return false;
while (*s && *p && *s == *p || *p == '?') {
++s;
++p;
}
if (*p == '*') {
while (*p == '*') ++p;
if (!*p) return true;
do {
while (*s && !(*s == *p || *p == '?')) ++s;
if (isMatch(s, p)) return true;
if (mustFail) return false;
++s;
} while (*s);
return false;
}
if (*p && !*s) {
mustFail = true;
}
return !*s && !*p;
}
};

Time complexity : O(mn)

Spatial complexity : O(1)( Regardless of the recursive stack overhead )

[OJ] Wildcard Matching (Hard) More articles about

  1. [Leetcode][Python]44:Wildcard Matching

    # -*- coding: utf8 -*-'''__author__ = 'dabay.wang@gmail.com' 44:Wildcard Matchinghttps://oj.leetcode ...

  2. 【LeetCode】44. Wildcard Matching (2 solutions)

    Wildcard Matching Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any ...

  3. LeetCode: Wildcard Matching Problem solving report

    Wildcard MatchingImplement wildcard pattern matching with support for '?' and '*'. '?' Matches any s ...

  4. 【leetcode】Wildcard Matching

    Wildcard Matching Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any ...

  5. LeetCode - 44. Wildcard Matching

    44. Wildcard Matching Problem's Link --------------------------------------------------------------- ...

  6. 44. Wildcard Matching

    subject : Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single charact ...

  7. [LeetCode] Wildcard Matching Answer key

    6. Wildcard Matching subject Implement wildcard pattern matching with support for '?' and '*'. '?' Matche ...

  8. Regular Expression Matching & Wildcard Matching

    Regular Expression Matching Implement regular expression matching with support for '.' and '*'. '.' ...

  9. [LeetCode][Facebook Interview questions ] Wildcard matching and regular expression matching , topic Wildcard Matching

    The opening There are two types of matching , One is regular expression matching ,pattern Contains some keywords , such as '*' The usage of is closely followed by pattern After a character of , Indicates that this character can appear any number of times ( Include 0 Time ). The other is wildcard matching , We are ...

Random recommendation

  1. [Mindjet MindManager] Shortcut key operation of mind map

    originate :http://www.cnblogs.com/whylaughing/p/5530935.html Mindjet MindManager( Mind mapping ) The shortcut keys are as follows : Insert or CTR ...

  2. The host name links the database , Can't generate SSPI Context

    Two sets of Server, The environment is the same , All use the same domain account . 1 Of SQL Server Can pass Windows Authentication connects to 2, but 2 adopt Windows Authentication connection 1 Times the following mistakes : The target principal name is incorrect , Can't generate SSPI Up and down ...

  3. Android-- Enter auto prompt AutoCompleteTextView

    Layout file : <TextView android:id="@+id/title" android:layout_width="wrap_content" a ...

  4. nginx Learning notes 1

    Nginx It's using c language-written , see nginx Compile time parameter setting   Use nginx -V Command view have access to nginx -h Command view command help In the configuration file worker process Bound to the cpu On a specific kernel of ...

  5. Wechat mobile front-end development package capture debugging tool fiddler Use the tutorial

    In the circle of friends to see a crazy H5 Little games , to want to copy, what ? It can only be opened in wechat ? Sample , too young too simple , Limit oauth. Open it in wechat browser , I can still see your source code ~ Use fiddler Grab the bag You need to do some simple preparation first : ...

  6. Lazy&lt;T&gt; stay Entity Framework Performance optimization practices in

    Lazy<T> stay Entity Framework Performance optimization practices in ( Source code attached ) 2013-10-27 18:12 by JustRun, 328  read , 4  Comment on ,  Collection ,  edit In the use of EF Of ...

  7. Openlayer 3 Layer list control ( Customize )

    <body><div id="map"></div><div id="layerControl" class=&quo ...

  8. Elasticsearch Note 4 configuration parameters and core concepts

    stay es There is a... In the root directory config Catalog , There are two files in this directory elasticsearch.yml and logging.yml. logging.yml It's a log file ,es Is also used log4j To keep a journal , I am here ...

  9. The sixth week teaching assistant work summary ——NWNU Li Hongyi

    Homework should be corrected this week 23 Share , Actually marking homework 23 Share . This week's assignment requires :https://www.cnblogs.com/nwnu-daizh/p/10569690.html This week's problems : One .github Iterated ...

  10. Pascal Language ( The archive )

    data type Standard functions Operators and Expressions Input statement Output statement if sentence case sentence for sentence while sentence repeat sentence Function and process Formal parameter and actual parameter Global variables and local variables Array character string enumeration Subkingdom aggregate ...