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