สมมติว่าเรามีสตริงที่มีตัวเลขตั้งแต่ 2-9 ขึ้นไป เราต้องส่งคืนชุดตัวอักษรที่เป็นไปได้ทั้งหมดที่ตัวเลขสามารถแสดงได้ การจับคู่ตัวเลขกับตัวอักษรหนึ่งตัว (เหมือนกับบนปุ่มโทรศัพท์) แสดงไว้ด้านล่าง โปรดทราบว่า 1 ไม่ได้จับคู่กับตัวอักษรใดๆ
| 1 | 2 a b c | 3 d e f |
| 4 จี เฮ้ | 5 เจเคแอล | 6 m n o |
| 7 p q r s | 8 t u v | 9 w x y z |
| * | 0 | # |
ตัวอย่างเช่น หากสตริงที่ระบุคือ "23" สตริงที่เป็นไปได้จะเป็น ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce ”, “cf”]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดอาร์เรย์ที่เรียกว่า Solve เพื่อแก้ปัญหาแบบวนซ้ำ
- วิธีแก้ใช้ตัวเลข อักขระ ผลลัพธ์ current_string และ current_level ฟังก์ชันจะเป็นเช่นไร
- ถ้า current_level =ความยาวของตัวเลข ให้เพิ่มสตริงปัจจุบันหลังผลลัพธ์ แล้วส่งคืน
- สำหรับอักขระทั้งหมด i ในอักขระ[digits[current_level]]
- ดำเนินการแก้ไข (ตัวเลข, อักขระ, ผลลัพธ์, current_string + i, current_level + 1)
- การใช้งานจริงจะเป็นแบบ
- ถ้าความยาวหลักเป็น 0 ให้คืนค่ารายการว่าง
- กำหนดหนึ่งแผนที่เพื่อเก็บตัวเลขและอักขระที่เกี่ยวข้องเป็นสตริง
- ผลลัพธ์ :=รายการว่าง
- แก้การโทร (ตัวเลข, อักขระ, ผลลัพธ์, “”, 0)
ตัวอย่าง(Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution(object):
def letterCombinations(self, digits):
if len(digits) == 0:
return []
characters = {2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz"}
result = []
self.solve(digits,characters,result)
return result
def solve(self, digits, characters, result, current_string="",current_level = 0):
if current_level == len(digits):
result.append(current_string)
return
for i in characters[int(digits[current_level])]:
self.solve(digits,characters,result,current_string+i,current_level+1)
ob1 = Solution()
print(ob1.letterCombinations("37")) อินพุต
"37"
ผลลัพธ์
["dp","dq","dr","ds","ep","eq","er","es","fp","fq","fr","fs"]
