add a solution for 1087

fishercoder1534 · fishercoder1534 · commit 10875dda7765 · 2022-01-17T09:53:23.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_1087.java b/src/main/java/com/fishercoder/solutions/_1087.java
@@ -2,12 +2,13 @@
 
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collections;
 import java.util.List;
 
 public class _1087 {
     public static class Solution1 {
-        public String[] expand(String S) {
-            List<char[]> letters = parse(S);
+        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);
@@ -51,4 +52,49 @@ private List<char[]> parse(String s) {
             return result;
         }
     }
+
+    public static class Solution2 {
+        /**
+         * My completely original solution on 1/17/2022.
+         */
+        public String[] expand(String s) {
+            List<String> list = new ArrayList<>();
+            list.add("");
+            for (int i = 0; i < s.length(); i++) {
+                List<String> newList = new ArrayList<>();
+                if (s.charAt(i) == '{') {
+                    int j = i + 1;
+                    while (s.charAt(j) != '}') {
+                        j++;
+                    }
+                    String s2 = s.substring(i + 1, j);
+                    String[] chars = s2.split("\\,");
+                    for (String c : chars) {
+                        for (String sb : list) {
+                            sb += c;
+                            newList.add(sb);
+                        }
+                    }
+                    i = j;
+                } else {
+                    for (String sb : list) {
+                        sb += s.charAt(i);
+                        newList.add(sb);
+                    }
+                }
+                list.clear();
+                list.addAll(newList);
+            }
+            List<String> res = new ArrayList<>();
+            for (String sb : list) {
+                res.add(sb);
+            }
+            Collections.sort(res);
+            String[] ans = new String[res.size()];
+            for (int i = 0; i < res.size(); i++) {
+                ans[i] = res.get(i);
+            }
+            return ans;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_1087Test.java b/src/test/java/com/fishercoder/_1087Test.java
@@ -8,25 +8,30 @@
 
 public class _1087Test {
     private static _1087.Solution1 solution1;
+    private static _1087.Solution2 solution2;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _1087.Solution1();
+        solution2 = new _1087.Solution2();
     }
 
     @Test
     public void test1() {
         assertArrayEquals(new String[]{"ade", "adf", "bde", "bdf", "cde", "cdf"}, solution1.expand("{a,b,c}d{e,f}"));
+        assertArrayEquals(new String[]{"ade", "adf", "bde", "bdf", "cde", "cdf"}, solution2.expand("{a,b,c}d{e,f}"));
     }
 
     @Test
     public void test2() {
         assertArrayEquals(new String[]{"abcd"}, solution1.expand("abcd"));
+        assertArrayEquals(new String[]{"abcd"}, solution2.expand("abcd"));
     }
 
     @Test
     public void test3() {
         assertArrayEquals(new String[]{"acdf", "acef", "bcdf", "bcef"}, solution1.expand("{a,b}c{d,e}f"));
+        assertArrayEquals(new String[]{"acdf", "acef", "bcdf", "bcef"}, solution2.expand("{a,b}c{d,e}f"));
     }
 
 }

Original file line number	Diff line number	Diff line change
`@@ -8,25 +8,30 @@`
`8`	`8`
`9`	`9`	`public class _1087Test {`
`10`	`10`	`private static _1087.Solution1 solution1;`
	`11`	`+ private static _1087.Solution2 solution2;`
`11`	`12`
`12`	`13`	`@BeforeClass`
`13`	`14`	`public static void setup() {`
`14`	`15`	`solution1 = new _1087.Solution1();`
	`16`	`+ solution2 = new _1087.Solution2();`
`15`	`17`	`}`
`16`	`18`
`17`	`19`	`@Test`
`18`	`20`	`public void test1() {`
`19`	`21`	`assertArrayEquals(new String[]{"ade", "adf", "bde", "bdf", "cde", "cdf"}, solution1.expand("{a,b,c}d{e,f}"));`
	`22`	`+ assertArrayEquals(new String[]{"ade", "adf", "bde", "bdf", "cde", "cdf"}, solution2.expand("{a,b,c}d{e,f}"));`
`20`	`23`	`}`
`21`	`24`
`22`	`25`	`@Test`
`23`	`26`	`public void test2() {`
`24`	`27`	`assertArrayEquals(new String[]{"abcd"}, solution1.expand("abcd"));`
	`28`	`+ assertArrayEquals(new String[]{"abcd"}, solution2.expand("abcd"));`
`25`	`29`	`}`
`26`	`30`
`27`	`31`	`@Test`
`28`	`32`	`public void test3() {`
`29`	`33`	`assertArrayEquals(new String[]{"acdf", "acef", "bcdf", "bcef"}, solution1.expand("{a,b}c{d,e}f"));`
	`34`	`+ assertArrayEquals(new String[]{"acdf", "acef", "bcdf", "bcef"}, solution2.expand("{a,b}c{d,e}f"));`
`30`	`35`	`}`
`31`	`36`
`32`	`37`	`}`