update 17

fishercoder1534 · fishercoder1534 · commit c8ca38eac50a · 2021-10-11T17:27:26.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_17.java b/src/main/java/com/fishercoder/solutions/_17.java
@@ -34,4 +34,33 @@ List<String> combine(String letters, List<String> result) {
             return newResult;
         }
     }
+
+    public static class Solution2 {
+        /**
+         * My completely solution on 10/11/2021, no backtracking involved.
+         */
+        public List<String> letterCombinations(String digits) {
+            List<String> ans = new ArrayList<>();
+            if (digits.length() == 0 || digits.equals("")) {
+                return ans;
+            }
+            String[] options = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
+            ans.add("");
+            return recursion(ans, options, digits, 0);
+        }
+
+        private List<String> recursion(List<String> ans, String[] options, String digits, int index) {
+            if (index >= digits.length()) {
+                return ans;
+            }
+            List<String> newAns = new ArrayList<>();
+            String candidates = options[Integer.parseInt(digits.charAt(index) + "")];
+            for (String str : ans) {
+                for (int i = 0; i < candidates.length(); i++) {
+                    newAns.add(str + candidates.charAt(i));
+                }
+            }
+            return recursion(newAns, options, digits, index + 1);
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_17Test.java b/src/test/java/com/fishercoder/_17Test.java
@@ -8,34 +8,35 @@
 import java.util.Arrays;
 import java.util.List;
 
+import static org.assertj.core.api.Assertions.assertThat;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertTrue;
 
 public class _17Test {
     private static _17.Solution1 solution1;
+    private static _17.Solution2 solution2;
     private static String digits;
     private static List<String> expected;
-    private static List<String> actual;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _17.Solution1();
+        solution2 = new _17.Solution2();
     }
 
     @Test
     public void test1() {
         digits = "2";
-        actual = solution1.letterCombinations(digits);
         expected = new ArrayList<>(Arrays.asList("a", "b", "c"));
-        assertEquals(expected, actual);
+        assertThat(expected).hasSameElementsAs(solution1.letterCombinations(digits));
+        assertThat(expected).hasSameElementsAs(solution2.letterCombinations(digits));
     }
 
     @Test
     public void test2() {
         digits = "23";
-        actual = solution1.letterCombinations(digits);
         expected = new ArrayList<>(Arrays.asList("ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"));
-        /**order doesn't matter, so we check like below*/
-        assertTrue(expected.containsAll(actual) && actual.containsAll(expected));
+        assertThat(expected).hasSameElementsAs(solution1.letterCombinations(digits));
+        assertThat(expected).hasSameElementsAs(solution2.letterCombinations(digits));
     }
 }
