Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 25
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Implement regular expression matching with the following special characters:

. (period) which matches any single character
\* (asterisk) which matches zero or more of the preceding element
That is, implement a function that takes in a string and a valid regular expression and returns whether or not the string matches the regular expression.

For example, given the regular expression "ra." and the string "ray", your function should return true. The same regular expression on the string "raymond" should return false.

Given the regular expression ".*at" and the string "chat", your function should return true. The same regular expression on the string "chats" should return false.

Pull request description:
Day25
Resolves #59 

Patch:
diff --git a/README.md b/README.md
index ce0ca19..c397b80 100644
--- a/README.md
+++ b/README.md
@@ -38,3 +38,4 @@ problems from
 * [Day 22](https://github.com/vaskoz/dailycodingproblem-go/issues/53)
 * [Day 23](https://github.com/vaskoz/dailycodingproblem-go/issues/55)
 * [Day 24](https://github.com/vaskoz/dailycodingproblem-go/issues/57)
+* [Day 25](https://github.com/vaskoz/dailycodingproblem-go/issues/59)
diff --git a/day21/problem.go b/day21/problem.go
index cb9d6d6..65f4d94 100644
--- a/day21/problem.go
+++ b/day21/problem.go
@@ -13,7 +13,7 @@ type lectureEvent struct {
 	starting bool
 }
 
-// MinimumRooms calculates the minimum number of rooms to accomodate
+// MinimumRooms calculates the minimum number of rooms to accommodate
 // overlapping schedules.
 // Runtime is O(N log N) with O(2N) space
 func MinimumRooms(lectures []Lecture) int {
diff --git a/day25/problem.go b/day25/problem.go
new file mode 100644
index 0000000..4dea70d
--- /dev/null
+++ b/day25/problem.go
@@ -0,0 +1,30 @@
+package day25
+
+// Match returns if there is a regex match on the given input.
+func Match(input, pattern string) bool {
+	var ii, pi, missed int
+	for ii < len(input) && pi < len(pattern) && missed < 2 {
+		if pattern[pi] == '*' {
+			prev := pattern[pi-1]
+			var next byte
+			if pi+1 < len(pattern) {
+				next = pattern[pi+1]
+			}
+			for ii < len(input) && input[ii] != next {
+				if prev != '.' && input[ii] != prev {
+					return false
+				}
+				ii++
+			}
+			if ii == len(input) && pi < len(pattern)-1 {
+				return false
+			}
+			ii--
+		} else if pattern[pi] != '.' && input[ii] != pattern[pi] {
+			missed++
+		}
+		ii++
+		pi++
+	}
+	return ii == len(input) && pi == len(pattern)
+}


Test patch:
diff --git a/day25/problem_test.go b/day25/problem_test.go
new file mode 100644
index 0000000..8b9d706
--- /dev/null
+++ b/day25/problem_test.go
@@ -0,0 +1,36 @@
+package day25
+
+import "testing"
+
+var testcases = []struct {
+	input, pattern string
+	expected       bool
+}{
+	{"ray", "ra.", true},
+	{"raymond", "ra.", false},
+	{"chat", ".*at", true},
+	{"chats", ".*at", false},
+	{"chaaaa", "cha*", true},
+	{"raymond", "ra.*", true},
+	{"raymond", "ra.*d", true},
+	{"chaaab", "cha*", false},
+	{"chaaa", "cha*b", false},
+	{"abcd", "efg", false},
+	{"ab", "e", false},
+}
+
+func TestMatch(t *testing.T) {
+	for _, tc := range testcases {
+		if result := Match(tc.input, tc.pattern); result != tc.expected {
+			t.Errorf("Given (%v, %v), expected %v got %v", tc.input, tc.pattern, tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkMatch(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			Match(tc.input, tc.pattern)
+		}
+	}
+}