jinhuang1102

17. Letter Combinations of a Phone Number

Jan 22nd, 2019
271
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.95 KB | None | 0 0
  1. """
  2. 4/12/2019 复习这道题,这应该是第三遍做这道题了。
  3. 我做这道题的思路,有些技巧,一开始真的忘了之前是怎么做的了。 看了上一次的笔记才大概想起来。我这次再整理一遍思路吧。
  4.  
  5. 这道题让我们遍历所有的 digit to letters 的可能,思路大概是这样的。
  6.  
  7. for example: "234"
  8. 1. 首先我们把第一个digit所对应的字母,写到一个list里面,这样方便我们往每一个letter后面 加/减 随后的letter。此时我们的list里面应该是:
  9. ['a', 'b', 'c']
  10.  
  11. 2. 之后我们遍历 "34",digit 3 所对应的letters是"def",append到list中。这里我们要先求一下当前list的长度num。
  12.   2-1. 当遍历letters[0]的时候,我们把list的每一个element后面都加上letters[0]。此时我们的list里面应该是:['ad', 'bd', 'cd']
  13.   2-2. 之后,我们按照之前list的长度,把每一个index的值进行更改,然后再append到list末尾。更改的意思是 list[i][:-1] + letters[j]。此时我们的list里面是:['ad', 'bd', 'cd','ae', 'be', 'ce']
  14.  
  15. 3. 返回list
  16. """
  17.  
  18. """
  19. 17. Letter Combinations of a Phone Number 运用iteration的方法解决backtrack的问题
  20. 1. 首先建立keypad 与 letters 的 dictionary 映射。
  21. 2. 然后设立一个temp的list,把input string 的第一个keypad所对应数字装进list。这个list在之后会每次循环迭代。
  22. 3. 之后,从index 1 开始遍历数组,每遍历一位,现拿到映射letters,然后把映射letters的第一个值“+”到list当前的所有已生成的string上。当遍历后面的letter的时候把所有的string删除掉最后一位,再加上当前letter后,append到list的尾部。
  23. 4. 所以,每次遍历一个新的key的时候拿到当前list的size很重要,因为这样不会影响到新append的值。
  24. """
  25. class Solution(object):
  26.     def __init__(self):
  27.         self.keypad = {}
  28.         self.keypad['2'] = "abc"
  29.         self.keypad['3'] = "def"
  30.         self.keypad['4'] = "ghi"
  31.         self.keypad['5'] = "jkl"
  32.         self.keypad['6'] = "mno"
  33.         self.keypad['7'] = "pqrs"
  34.         self.keypad['8'] = "tuv"
  35.         self.keypad['9'] = "wxyz"    
  36.    
  37.     def letterCombinations(self, digits):
  38.         """
  39.        :type digits: str
  40.        :rtype: List[str]
  41.        """
  42.         if not digits:
  43.             return []
  44.        
  45.         temp = []
  46.         letters = self.keypad[digits[0]]
  47.         for i in range(0, len(letters)):
  48.             temp.append(letters[i])
  49.        
  50.         for i in range(1, len(digits)):
  51.             s = self.keypad[digits[i]]
  52.            
  53.             num = len(temp)
  54.            
  55.             for j in range(0, len(s)):
  56.                 if j == 0:
  57.                     for k in range(0, num):
  58.                         temp[k] += s[j]
  59.                 else:
  60.                     for k in range(0, num):
  61.                         temp.append(temp[k][:-1] + s[j])
  62.                        
  63.         return temp
Advertisement
Add Comment
Please, Sign In to add comment