Letter Combinations of a Phone Number

Jack-Cherish · Jack-Cherish · commit f1faf1af1141 · 2017-09-11T10:07:54.000+08:00
diff --git a/String/Medium/17.Letter Combinations of a Phone Number.md b/String/Medium/17.Letter Combinations of a Phone Number.md
@@ -0,0 +1,80 @@
+# 题目
+
+给定一个数字字符串，返回所有数字代表的所有字母组合结果。
+
+数字到字母的映射，就像电话按钮一样。
+```python
+        kvmaps = {
+            '2': 'abc',
+            '3': 'def',
+            '4': 'ghi',
+            '5': 'jkl',
+            '6': 'mno',
+            '7': 'pqrs',
+            '8': 'tuv',
+            '9': 'wxyz'
+        }
+```
+
+**例子：**
+
+	Input:Digit string "23"
+	Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
+
+# 思考
+就是遍历所有可能组合，一个简单的方法是使用reduce函数
+
+**代码：**
+
+普通遍历方法：
+
+```python
+class Solution(object):
+    def letterCombinations(self, digits):
+        """
+        :type digits: str
+        :rtype: List[str]
+        """
+        if '' == digits: return []
+        kvmaps = {
+            '2': 'abc',
+            '3': 'def',
+            '4': 'ghi',
+            '5': 'jkl',
+            '6': 'mno',
+            '7': 'pqrs',
+            '8': 'tuv',
+            '9': 'wxyz'
+        }
+        ret=['']
+        for c in digits:
+            tmp=[]
+            for y in ret:
+                for x in kvmaps[c]:
+                    tmp.append(y+x)
+            ret=tmp
+        return ret
+```
+
+使用reduce
+
+```python
+class Solution(object):
+    def letterCombinations(self, digits):
+        """
+        :type digits: str
+        :rtype: List[str]
+        """
+        if '' == digits: return []
+        kvmaps = {
+            '2': 'abc',
+            '3': 'def',
+            '4': 'ghi',
+            '5': 'jkl',
+            '6': 'mno',
+            '7': 'pqrs',
+            '8': 'tuv',
+            '9': 'wxyz'
+        }
+        return reduce(lambda acc, digit: [x + y for x in acc for y in kvmaps[digit]], digits, [''])
+```
