LeetCode in Kotlin
44. Wildcard Matching
Hard
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:
'?'Matches any single character.'*'Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Example 1:
Input: s = “aa”, p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.
Example 2:
Input: s = “aa”, p = “*”
Output: true
Explanation: ‘*’ matches any sequence.
Example 3:
Input: s = “cb”, p = “?a”
Output: false
Explanation: ‘?’ matches ‘c’, but the second letter is ‘a’, which does not match ‘b’.
Constraints:
0 <= s.length, p.length <= 2000scontains only lowercase English letters.pcontains only lowercase English letters,'?'or'*'.
Solution
class Solution {
fun isMatch(s: String, p: String): Boolean {
var i = 0
var j = 0
var starIdx = -1
var lastMatch = -1
while (i < s.length) {
if (j < p.length &&
(s[i] == p[j] || p[j] == '?')
) {
i++
j++
} else if (j < p.length && p[j] == '*') {
starIdx = j
lastMatch = i
j++
} else if (starIdx != -1) {
// there is a no match and there was a previous star, we will reset the j to indx
// after star_index
// lastMatch will tell from which index we start comparing the string if we
// encounter * in pattern
j = starIdx + 1
// we are saying we included more characters in * so we incremented the
lastMatch++
// index
i = lastMatch
} else {
return false
}
}
var isMatch = true
while (j < p.length && p[j] == '*') {
j++
}
if (i != s.length || j != p.length) {
isMatch = false
}
return isMatch
}
}