Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/1bb7f012425a56001d698f13020fb848 to your computer and use it in GitHub Desktop.
Save jianminchen/1bb7f012425a56001d698f13020fb848 to your computer and use it in GitHub Desktop.
Leetcode 10 - regular expression match - peer explained to me his idea using one iteration on pattern text - not dynamic programming
// My solution:
func isMatch(text: String, pattern: String) -> Bool {
var i: Int = 0
var textIndex: Int = 0
while i < pattern.count && textIndex < text.count {
let currPat = Array(pattern)[i]
var nextPat: String.Element = " "
if i < pattern.count - 1
{
nextPat = Array(pattern)[i+1]
}
if nextPat == "*" {
var matchPat = currPat
if currPat == "."
{
matchPat = Array(text)[textIndex]
} // if ".*" pattern, save first item in sequence
while textIndex < text.count && matchPat == Array(text)[textIndex] { // match 0+ times
textIndex += 1 // match at least 1 time
}
i += 1 // extra increment to skip star
}
else if currPat != Array(text)[textIndex] && currPat != "."
{
return false
}
else {
textIndex += 1 // match 1 time
}
i += 1 // advance pattern index
}
// Handle case if pattern ends with "*" with element count of 0
if i < pattern.count - 1 && Array(pattern)[i+1] == "*" { i += 2 }
return textIndex == text.count && i == pattern.count
}
print(isMatch(text: "acdddd", pattern: "ab*c.*"))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment