add 1087

fishercoder1534 · fishercoder1534 · commit 3da4dcd15554 · 2020-02-17T07:26:17.000-08:00
diff --git a/README.md b/README.md
@@ -98,6 +98,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1100|[Find K-Length Substrings With No Repeated Characters](https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1100.java) | |Medium|String, Sliding Window|
 |1099|[Two Sum Less Than K](https://leetcode.com/problems/two-sum-less-than-k/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1099.java) |  [:tv:](https://www.youtube.com/watch?v=2Uq7p7HE0TI)|Easy||
 |1089|[Duplicate Zeros](https://leetcode.com/problems/duplicate-zeros/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1089.java) | |Easy||
+|1087|[Brace Expansion](https://leetcode.com/problems/brace-expansion/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1087.java) | |Medium|Backtracking|
 |1086|[High Five](https://leetcode.com/problems/high-five/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1086.java) | [:tv:](https://www.youtube.com/watch?v=3iqC5J4l0Cc)|Easy||
 |1085|[Sum of Digits in the Minimum Number](https://leetcode.com/problems/sum-of-digits-in-the-minimum-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1085.java)| [:tv:](https://www.youtube.com/watch?v=GKYmPuHZpQg)|Easy||
 |1079|[Letter Tile Possibilities](https://leetcode.com/problems/letter-tile-possibilities/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1079.java)| |Medium||
diff --git a/src/main/java/com/fishercoder/solutions/_1087.java b/src/main/java/com/fishercoder/solutions/_1087.java
@@ -0,0 +1,78 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+/**
+ * 1087. Brace Expansion
+ *
+ * A string S represents a list of words.
+ * Each letter in the word has 1 or more options.  If there is one option, the letter is represented as is.
+ * If there is more than one option, then curly braces delimit the options.
+ * For example, "{a,b,c}" represents options ["a", "b", "c"].
+ * For example, "{a,b,c}d{e,f}" represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"].
+ *
+ * Return all words that can be formed in this manner, in lexicographical order.
+ *
+ * Example 1:
+ * Input: "{a,b}c{d,e}f"
+ * Output: ["acdf","acef","bcdf","bcef"]
+ *
+ * Example 2:
+ * Input: "abcd"
+ * Output: ["abcd"]
+ *
+ * Note:
+ * 1 <= S.length <= 50
+ * There are no nested curly brackets.
+ * All characters inside a pair of consecutive opening and ending curly brackets are different.
+ * */
+public class _1087 {
+    public static class Solution1 {
+        public String[] expand(String S) {
+            List<char[]> letters = parse(S);
+            List<String> result = backtracking(letters, 0, new StringBuilder(), new ArrayList<>());
+            String[] r = result.stream().toArray(String[]::new);
+            Arrays.sort(r);
+            return r;
+        }
+
+        private List<String> backtracking(List<char[]> letters, int start, StringBuilder sb, List<String> result) {
+            if (start >= letters.size()) {
+                result.add(sb.toString());
+                return result;
+            }
+            char[] chars = letters.get(start);
+            for (int i = 0; i < chars.length; i++) {
+                sb.append(chars[i]);
+                backtracking(letters, start + 1, sb, result);
+                sb.setLength(sb.length() - 1);
+            }
+            return result;
+        }
+
+        private List<char[]> parse(String s) {
+            List<char[]> result = new ArrayList<>();
+            for (int i = 0; i < s.length(); i++) {
+                if (s.charAt(i) == '{') {
+                    int start = ++i;
+                    while (i < s.length() && s.charAt(i) != '}') {
+                        i++;
+                    }
+                    String[] strings = s.substring(start, i).split(",");
+                    char[] chars = new char[strings.length];
+                    for (int j = 0; j < strings.length; j++) {
+                        chars[j] = strings[j].charAt(0);
+                    }
+                    result.add(chars);
+                } else {
+                    char[] chars = new char[1];
+                    chars[0] = s.charAt(i);
+                    result.add(chars);
+                }
+            }
+            return result;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1087Test.java b/src/test/java/com/fishercoder/_1087Test.java
@@ -0,0 +1,32 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1087;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertArrayEquals;
+
+public class _1087Test {
+    private static _1087.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1087.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertArrayEquals(new String[]{"ade", "adf", "bde", "bdf", "cde", "cdf"}, solution1.expand("{a,b,c}d{e,f}"));
+    }
+
+    @Test
+    public void test2() {
+        assertArrayEquals(new String[]{"abcd"}, solution1.expand("abcd"));
+    }
+
+    @Test
+    public void test3() {
+        assertArrayEquals(new String[]{"acdf", "acef", "bcdf", "bcef"}, solution1.expand("{a,b}c{d,e}f"));
+    }
+
+}
