Add solution for 1003 (fishercoder1534#50)

havanagrawal · fishercoder1534 · commit 6f57360a692f · 2019-04-24T14:34:10.000-07:00
diff --git a/README.md b/README.md
@@ -34,6 +34,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |1018|[Binary Prefix Divisible By 5](https://leetcode.com/problems/binary-prefix-divisible-by-5/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1018.java) | O(n) | O(1) | |Easy|
 |1013|[Pairs of Songs With Total Durations Divisible by 60](https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1013.java) | O(n) | O(1) | |Easy|
 |1009|[Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1009.java) | O(n) | O(1) | |Easy|
+|1003|[Check If Word Is Valid After Substitutions](https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1003.java) | O(n) | O(n) | |Medium|
 |1002|[Find Common Characters](https://leetcode.com/problems/find-common-characters/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1002.java) | O(n) | O(1) | |Easy|
 |999|[Available Captures for Rook](https://leetcode.com/problems/available-captures-for-rook/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_999.java) | O(1) | O(1) | |Easy|
 |997|[Find the Town Judge](https://leetcode.com/problems/find-the-town-judge/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_997.java) | O(n) | O(n) | |Easy| 
diff --git a/src/main/java/com/fishercoder/solutions/_1003.java b/src/main/java/com/fishercoder/solutions/_1003.java
@@ -0,0 +1,39 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayDeque;
+import java.util.Deque;
+
+/**
+ * 1003. Check If Word Is Valid After Substitutions
+ *
+ * We are given that the string "abc" is valid.
+ *
+ * From any valid string V, we may split V into two pieces X and Y such that X + Y (X concatenated with Y) is equal to V.  (X or Y may be empty.)  Then, X + "abc" + Y is also valid.
+ *
+ * If for example S = "abc", then examples of valid strings are: "abc", "aabcbc", "abcabc", "abcabcababcc".  Examples of invalid strings are: "abccba", "ab", "cababc", "bac".
+ *
+ * Return true if and only if the given string S is valid.
+ *
+ * Note:
+ *  * 1 <= S.length <= 20000
+ *  * S[i] is 'a', 'b', or 'c'
+ */
+
+public class _1003 {
+    public static class Solution1 {
+        public boolean isValid(String S) {
+            Deque<Character> stack = new ArrayDeque<>();
+
+            for (char c : S.toCharArray()) {
+                if (c == 'c') {
+                    if (stack.isEmpty() || stack.pop() != 'b') return false;
+                    if (stack.isEmpty() || stack.pop() != 'a') return false;
+                } else {
+                    stack.push(c);
+                }
+            }
+
+            return stack.isEmpty();
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1003Test.java b/src/test/java/com/fishercoder/_1003Test.java
@@ -0,0 +1,35 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1003;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+public class _1003Test {
+    private static _1003.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {solution1 = new _1003.Solution1();}
+
+    @Test
+    public void test1() {
+        assertTrue(solution1.isValid("aabcbc"));
+    }
+
+    @Test
+    public void test2() {
+        assertTrue(solution1.isValid("abcabcababcc"));
+    }
+
+    @Test
+    public void test3() {
+        assertFalse(solution1.isValid("abccba"));
+    }
+
+    @Test
+    public void test4() {
+        assertFalse(solution1.isValid("cababc"));
+    }
+}
