Created
February 11, 2018 18:44
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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