[leetcode 44] Wildcard Matching
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
类似于正則表達式的匹配,当中两个字符串为空为true。当中'?
'不能够替换空串,'*'能够替换空串。
AC代码:
class Solution { public: bool isMatch(string s, string p) { int len1=s.size(); int len2=p.size(); if(len1==0&&len2==0) return true; else if(len1==0) { int i=0; while(i<len2) { if(p[i]!='*') return false; else ++i; } return true; } else if(len2==0) return false; else { int i=0; int j=0; int pos_s=-1; int pos_p=-1; while(i<len1) { if(j<len2&&(s[i]==p[j]||p[j]=='?')) { ++i; ++j; } else if(j<len2&&p[j]=='*') { pos_s=i; pos_p=j; ++j; } else if(pos_p!=-1) { i=++pos_s; j=pos_p+1; // ++pos_s; } else return false; } while(j<len2&&(p[j]=='*')) ++j; if(j==len2) return true; else return false; } } };
其它Leetcode题目AC代码:https://github.com/PoughER/leetcode
相关文章
- leetcode 二分查找 Search in Rotated Sorted Array
- Leetcode 85.最大矩形(困难)
- [LeetCode] Decode Ways
- LeetCode 724. 寻找数组的中心索引
- 【LeetCode】44. Wildcard Matching (2 solutions)
- leetcode - Interleaving String
- 【leetcode】:109. 有序链表转换二叉搜索树
- [LeetCode] 1340. Jump Game V 跳跃游戏之五
- [LeetCode] 1103. Distribute Candies to People 给人们发糖果
- [LeetCode] 1130. Minimum Cost Tree From Leaf Values 叶值的最小代价生成树
- [LeetCode] 908. Smallest Range I 最小区间
- [LeetCode] 874. Walking Robot Simulation 走路机器人仿真
- [LeetCode] 421. Maximum XOR of Two Numbers in an Array 数组中异或值最大的两个数字
- [LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal 由先序和中序遍历建立二叉树