Implement wildcard pattern matching with support for '?'
and '*'
.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
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", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
例如:
abed
?b*d**
a=?, go on, b=b, go on,
e=*, save * position star=3, save s position match = 3, p++
e!=d, check if there was a *, yes, s=++match; p=star+1
d=d, go on, meet the end.
check the rest element in p, if all are *, true, else false;
C++代码比较简洁,java代码就麻烦点了。
public boolean isMatch(String s, String p) { int i = 0, j = 0; int m = s.length(), n = p.length(); int star = -1, match = 0; while(i<m) { if(j < n && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) { i++;j++; } else if(j<n && p.charAt(j) == '*') { star = j++; match = i; } else if(star != -1){ j = star + 1; i = ++match; } else { return false; } } while(j<n && p.charAt(j) == '*') { j++; } return j == n; }
bool isMatch(const char *s, const char *p) { const char* star=NULL; const char* ss=s; while (*s){ if ((*p=='?')||(*p==*s)){s++;p++;continue;} if (*p=='*'){star=p++; ss=s;continue;} if (star){ p = star+1; s=++ss;continue;} return false; } while (*p=='*'){p++;} return !*p; }
相关推荐
LeetCode 44. Wildcard Matching Wildcard Matching O(N) by Jimbowhy http://blog.csdn.net/WinsenJiansbomber/article/details/50862569 在 LeetCode 上看到第二个有趣的问题,是关于字符串匹配的,在接触过正则...
leetcode 答案 算法心得 大纲 解算法 = 思路->思路验证->直译->结果验证 进步 = 解算法->看高手答案->临摹->形成后续TODO ...容易跑偏,要直译,要直译,要直译!...很多都是可以直接求出来的...No.44(wildcard matching) No
通配符匹配leetcode Greedy-5 Problem1: Wildcard Matching () Problem2: Bikes in a Campus ()
leetcode中国 买卖股票 从easy一直问到hard 数独 从medium的判断是不是valid 到 hard的solve 数独 从BST里面删除一个node (要求写test case) design就是皮毛的问题。。。我几乎就是把Harvard那个intro system design...
wildcard matching 动态规划 longest common prefix , 简单 valid number, hard, 用有限自动机 integer to roman ,easy , 模拟 roman to integer ,easy , 模拟 count and say , easy , 模拟 Anagrams 字符串处理,map...
力码解决方案 Leetcode是一个网站,人们——主要是软件工程师——练习他们的编码技能。 有 800 多个问题(并且还在不断...├── Wildcard Matching │ ├── Readme.md │ └── solution.js ├── Valid Number │
密码leetcode的源代码...matchingpackage io.lcalmsky.leetcode. wildcard_matchingclass io.lcalmsky.leetcode. wildcard_matching.Solutiontest io.lcalmsky.leetcode. wildcard_matching.SolutionTest问题清
Wildcard Matching Python 2016/4/1 Hard 051 N-Queens C++ 2016/5/18 Hard 092 Reverse Linked List II Python 2017/11/28 Medium 095 Unique Binary Search Trees Python 2017/11/28 Medium 09
9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 13 Two Sum 47 14 Two Sum II Input array is sorted 49 15 Two Sum III Data structure design ...
Wildcard Matching Longest Common Prefix Valid Number Integer to Roman Roman to Integer Count and Say Anagrams Valid Anagram Simplify Path Length of Last Word Isomorphic Strings Word Pattern 栈和队列 ...