#leetcode#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

Two pointers..

https://leetcode.com/discuss/10133/linear-runtime-and-constant-space-solution

public class Solution {public boolean isMatch(String s, String p) {int i = 0, j = 0, starIdx = -1, match = 0;while( i < s.length()){// if current s[i] and p[j] match, s & both move forwardif(j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))){i++;j++;}// if p[j] is '*', mark index of '*' and current match index of s, which is current i, j++ which means current * is empty sequenceelse if(j < p.length() && p.charAt(j) == '*'){starIdx = j;match = i;j++;}// current s[i] and p[j] does not match, // and p[j] is not '*', then we'll see if there is any '*' in front of current j, // if not, return false, // if there is a '*', then move j back to the next char of '*', and move i back to the next of match position, // which is equal to '*' is matching only one character of s[match], // if the next loop still same case as this one, then the '*' will match two characters after match in s, and so on... else if(starIdx != -1){j = starIdx + 1;match++;i = match;}else{// here is the case: p[j] and s[i] doesn't match; // p[j] is not '*'; no '*' before current j. return false;return false;}}while(j < p.length() && p.charAt(j) == '*'){j++;}return j == p.length();}
}

Time complexity is O(n ^ 2)  ?.. not sure

Quote:

it is O(m*n) in worst cases, consider below input:

s = "aaaaaaaaaaaaaaaaaaaa"

p = "*aaaaaaaaaaaaaaaaaab"

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！