Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 27
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed).

For example, given the string `"([])[]({})"`, you should return true.

Given the string `"([)]"` or `"((()"`, you should return false.

Pull request description:
Day27
Resolves #63 .

Patch:
diff --git a/README.md b/README.md
index c999be4..e1beab5 100644
--- a/README.md
+++ b/README.md
@@ -40,3 +40,4 @@ problems from
 * [Day 24](https://github.com/vaskoz/dailycodingproblem-go/issues/57)
 * [Day 25](https://github.com/vaskoz/dailycodingproblem-go/issues/59)
 * [Day 26](https://github.com/vaskoz/dailycodingproblem-go/issues/61)
+* [Day 27](https://github.com/vaskoz/dailycodingproblem-go/issues/63)
diff --git a/day27/problem.go b/day27/problem.go
new file mode 100644
index 0000000..47fbc78
--- /dev/null
+++ b/day27/problem.go
@@ -0,0 +1,32 @@
+package day27
+
+// WellBalanced returns true if the brackets in the string are balanced and well-formed.
+// Runs in O(N) time where N is the number of runes. Using O(N/2) extra space.
+func WellBalanced(brackets string) bool {
+	openBrackets := make([]rune, 0, (len(brackets)/2)+1)
+	for _, r := range brackets {
+		if r == '(' || r == '[' || r == '{' {
+			openBrackets = append(openBrackets, r)
+		} else if r == ')' || r == ']' || r == '}' {
+			if len(openBrackets) == 0 {
+				return false
+			}
+			var pop rune
+			pop, openBrackets = openBrackets[len(openBrackets)-1], openBrackets[:len(openBrackets)-1]
+			if !IsMatch(pop, r) {
+				return false
+			}
+		}
+		if len(openBrackets) > len(brackets)/2 {
+			return false
+		}
+	}
+	return len(openBrackets) == 0
+}
+
+// IsMatch returns true if the left and right runes form a matching pair.
+func IsMatch(left, right rune) bool {
+	return (right == ')' && left == '(') ||
+		(right == ']' && left == '[') ||
+		(right == '}' && left == '{')
+}


Test patch:
diff --git a/day27/problem_test.go b/day27/problem_test.go
new file mode 100644
index 0000000..626f2ec
--- /dev/null
+++ b/day27/problem_test.go
@@ -0,0 +1,29 @@
+package day27
+
+import "testing"
+
+var testcases = []struct {
+	input    string
+	expected bool
+}{
+	{"([])[]({})", true},
+	{"([)]", false},
+	{"((()", false},
+	{"((())))", false},
+}
+
+func TestWellBalanced(t *testing.T) {
+	for _, tc := range testcases {
+		if result := WellBalanced(tc.input); result != tc.expected {
+			t.Errorf("Expected %v got %v for %v", tc.expected, result, tc.input)
+		}
+	}
+}
+
+func BenchmarkWellBalanced(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			WellBalanced(tc.input)
+		}
+	}
+}