17. Letter Combinations of a Phone Number - python3
4018 ワード
17. Letter Combinations of a Phone Number
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
My Answer 1: Accepted (Runtime: 28 ms - 82.26% / Memory Usage: 14.3 MB - 27.50%)
from itertools import product
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
def switch(ch):
return {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']
}.get(ch, -1)
if digits == "":
return []
if len(digits) == 1:
return switch(digits)
letter = []
for ch in digits:
letter.append(switch(ch))
combinations = list(product(*letter))
result = []
for i in combinations:
convertstr = ""
for j in range(0, len(digits)):
convertstr += i[j]
if convertstr != "":
result.append(convertstr)
return result
Pythonにはswitch文がないので関数にします.
各数値に対応する文字のリストを返します.
itertools import productを使うとリストの組み合わせが得られるので便利です.^^
リストの組合せを持つ組合せをstr組合せに変換してresultに入れて、車に戻って終わりました!
詳細については、Pythonでリスト内のすべての値を取得する組合せを参照してください:https://ourcstory.tistory.com/414
プロダクト関数を除いて、直接実現したいなら遡及を使うべきですが・・・my trauma.....
46.大会と78.Subsetsを参考にしてみたいのですが….私にとってイヴァンセワ...
Approach 1: Backtracking
Solution 1: Runtime: 32 ms - 56.43% / Memory Usage: 14.2 MB - 77.05%
class Solution:
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
phone = {'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']}
def backtrack(combination, next_digits):
# if there is no more digits to check
if len(next_digits) == 0:
# the combination is done
output.append(combination)
# if there are still digits to check
else:
# iterate over all letters which map
# the next available digit
for letter in phone[next_digits[0]]:
# append the current letter to the combination
# and proceed to the next digits
backtrack(combination + letter, next_digits[1:])
output = []
if digits:
backtrack("", digits)
return output
丸暗記
Reference
この問題について(17. Letter Combinations of a Phone Number - python3), 我々は、より多くの情報をここで見つけました
https://velog.io/@jsh5408/17.-Letter-Combinations-of-a-Phone-Number-python3
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
from itertools import product
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
def switch(ch):
return {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']
}.get(ch, -1)
if digits == "":
return []
if len(digits) == 1:
return switch(digits)
letter = []
for ch in digits:
letter.append(switch(ch))
combinations = list(product(*letter))
result = []
for i in combinations:
convertstr = ""
for j in range(0, len(digits)):
convertstr += i[j]
if convertstr != "":
result.append(convertstr)
return result
class Solution:
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
phone = {'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']}
def backtrack(combination, next_digits):
# if there is no more digits to check
if len(next_digits) == 0:
# the combination is done
output.append(combination)
# if there are still digits to check
else:
# iterate over all letters which map
# the next available digit
for letter in phone[next_digits[0]]:
# append the current letter to the combination
# and proceed to the next digits
backtrack(combination + letter, next_digits[1:])
output = []
if digits:
backtrack("", digits)
return output
Reference
この問題について(17. Letter Combinations of a Phone Number - python3), 我々は、より多くの情報をここで見つけました https://velog.io/@jsh5408/17.-Letter-Combinations-of-a-Phone-Number-python3テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol