สมมติว่าเรามีสตริงที่มีตัวเลขตั้งแต่ 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 | # |
ตัวอย่างเช่น หากสตริงที่ระบุคือ "49" สตริงที่เป็นไปได้จะเป็น ['gw', 'gx', 'gy', 'gz', 'hw', 'hx', 'hy', 'hz ', 'iw', 'ix', 'iy', 'iz']
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- กำหนดอาร์เรย์ที่เรียกว่า Solve เพื่อแก้ปัญหาแบบวนซ้ำ
- วิธีแก้ใช้ตัวเลข อักขระ ผลลัพธ์ current_string และ current_level ฟังก์ชันจะเป็นเช่นไร
- ถ้า current_level =ความยาวของตัวเลข ให้เพิ่มสตริงปัจจุบันหลังผลลัพธ์ แล้วส่งคืน
- สำหรับอักขระทั้งหมด i ในอักขระ[digits[current_level]]
- ดำเนินการแก้ไข (ตัวเลข, อักขระ, ผลลัพธ์, current_string + i, current_level + 1)
- การใช้งานจริงจะเป็นแบบ
- ถ้าความยาวหลักเป็น 0 ให้คืนค่ารายการว่าง
- กำหนดหนึ่งแผนที่เพื่อเก็บตัวเลขและอักขระที่เกี่ยวข้องเป็นสตริง
- ผลลัพธ์ :=รายการว่าง
- แก้การโทร (ตัวเลข, อักขระ, ผลลัพธ์, “”, 0)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
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("49")) อินพุต
"49"
ผลลัพธ์
['gw', 'gx', 'gy', 'gz', 'hw', 'hx', 'hy', 'hz', 'iw', 'ix', 'iy', 'iz']
