[DFS] add Solutions to Combination Sum and Letter Combinations of a Phone Number

Yi Gu · Yi Gu · commit 074dc16a2e4f · 2016-06-01T22:16:16.000-07:00
diff --git a/DFS/CombinationSum.swift b/DFS/CombinationSum.swift
@@ -0,0 +1,41 @@
+/**
+ * Question Link: https://leetcode.com/problems/combination-sum/
+ * Primary idea: Classic Depth-first Search
+ * 
+ * Time Complexity: O(n^n), Space Complexity: O(n)
+ *
+ */
+
+class CombinationSum {
+    func combinationSum(candidates: [Int], _ target: Int) -> [[Int]] {
+        var res = [[Int]]()
+        
+        guard candidates.count > 0 else {
+            return res
+        }
+    
+        var path = [Int]()
+        let candidates = candidates.sort({$0 < $1})
+        
+        _dfs(candidates, target, &res, &path, 0)
+        
+        return res
+    }
+    
+    private func _dfs(candidates: [Int], _ target: Int, inout _ res: [[Int]], inout _ path: [Int], _ index: Int) {
+        if target == 0 {
+            res.append([Int](path))
+            return
+        }
+        
+        for i in index ..< candidates.count {
+            guard candidates[i] <= target else {
+                break
+            }
+            
+            path.append(candidates[i])
+            _dfs(candidates, target - candidates[i], &res, &path, i)
+            path.removeLast()
+        }
+    }
+}
diff --git a/DFS/LetterCombinationsPhoneNumber.swift b/DFS/LetterCombinationsPhoneNumber.swift
@@ -0,0 +1,59 @@
+/**
+ * Question Link: https://leetcode.com/problems/letter-combinations-of-a-phone-number/
+ * Primary idea: Classic Depth-first Search, create phone board at first
+ * 
+ * Time Complexity: O(nm), m stands for the average size of a string represented by a number 
+ * Space Complexity: O(n)
+ *
+ */
+
+class LetterCombinationsPhoneNumber {
+    func letterCombinations(digits: String) -> [String] {
+        var res = [String]()
+        let chars = [Character](digits.characters)
+        
+        guard chars.count > 0 else {
+            return res
+        }
+        
+        let board = _init()
+        
+        _dfs(&res, board, chars, "", 0)
+        
+        return res
+    }
+    
+    private func _init() -> [String] {
+        var res = [String]()
+        
+        res.append("")
+        res.append("")
+        res.append("abc")
+        res.append("def")
+        res.append("ghi")
+        res.append("jkl")
+        res.append("mno")
+        res.append("pqrs")
+        res.append("tuv")
+        res.append("wxyz")
+        
+        return res
+    }
+    
+    private func _dfs(inout res: [String], _ board: [String], _ chars: [Character], _ temp: String, _ index: Int) {
+        // termination case
+        if index == chars.count {
+            res.append(temp)
+            return
+        }
+        
+        var temp = temp
+        let current = [Character](board[Int(String(chars[index]))!].characters)
+        
+        for i in 0 ..< current.count {
+            temp += String(current[i])
+            _dfs(&res, board, chars, temp, index + 1)
+            temp = String(temp.characters.dropLast())
+        }
+    }
+}
