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
- [Leetcode][Python]44：Wildcard Matching
# -*- coding: utf8 -*-'''__author__ = 'dabay.wang@gmail.com' 44:Wildcard Matchinghttps://oj.leetcode ...
- 【LeetCode】44. Wildcard Matching (2 solutions)
Wildcard Matching Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any ...
- LeetCode: Wildcard Matching Problem solving report
Wildcard MatchingImplement wildcard pattern matching with support for '?' and '*'. '?' Matches any s ...
- 【leetcode】Wildcard Matching
Wildcard Matching Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any ...
- LeetCode - 44. Wildcard Matching
44. Wildcard Matching Problem's Link --------------------------------------------------------------- ...
- 44. Wildcard Matching
subject : Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single charact ...
- [LeetCode] Wildcard Matching Answer key
6. Wildcard Matching subject Implement wildcard pattern matching with support for '?' and '*'. '?' Matche ...
- Regular Expression Matching & Wildcard Matching
Regular Expression Matching Implement regular expression matching with support for '.' and '*'. '.' ...
- [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
- [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 ...
- 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 ...
- Android-- Enter auto prompt AutoCompleteTextView
Layout file : <TextView android:id="@+id/title" android:layout_width="wrap_content" a ...
- 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 ...
- 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 : ...
- Lazy<T> 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 ...
- Openlayer 3 Layer list control ( Customize )
<body><div id="map"></div><div id="layerControl" class=&quo ...
- 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 ...
- 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 ...
- 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 ...