Python - หาสตริงทั้งหมดจากการ Map ตัวอักษรจากตัวเลข

มี character mapping สำหรับตัวเลข 1-9:

1 → [A, B, C]     2 → [D, E, F]     3 → [G, H, I]
4 → [J, K, L]     5 → [M, N, O]     6 → [P, Q, R]
7 → [S, T, U]     8 → [V, W, X]     9 → [Y, Z]

ได้ตัวเลข (ไม่มี 0) ต้องแทนที่แต่ละหลักด้วยตัวอักษรที่ map ไป พร้อมเงื่อนไข: หลักเดียวกันต้องใช้ตัวอักษรเดียวกัน (consistent mapping)

ตัวอย่าง

Input: [4, 3, 5]

Output: JGM KGM LGM JHM KHM LHM JIM KIM LIM JGN KGN LGN JHN KHN LHN JIN KIN LIN JGO KGO LGO JHO KHO LHO JIO KIO LIO

อัลกอริธึม

1. Track mapping จาก digit → character index ที่เลือก
2. สร้าง combinations แบบ incremental
3. ถ้าดีเจอร์ซ้ำ ใช้ character index เดียวกับครั้งแรก

Python Implementation

def find_combinations(inp, table):
    """
    inp: list of digits (1-9)
    table: list of lists, table[digit-1] = characters for that digit
    """
    out = []
    temp = []
    char_map = {}  # digit -> chosen index
    index = 0      # position in input
    
    for digit in inp:
        # Record first occurrence position
        if digit not in char_map:
            char_map[digit] = index
        
        temp.clear()
        
        for i in range(len(table[digit - 1])):
            char = table[digit - 1][i]
            
            if index == 0:
                # First digit: start new strings
                out.append(char)
            
            else:
                # Subsequent digits: extend existing strings
                for string in out:
                    # If this digit appeared before, use SAME character
                    if char_map[digit] != index:
                        # Use character from first occurrence position
                        char = string[char_map[digit]]
                    
                    new_string = string + char
                    temp.append(new_string)
                
                # If digit mapped before, no need to try other characters
                if char_map[digit] != index:
                    break
        
        if index > 0:
            out = temp.copy()
        
        index += 1
    
    return out

# Mapping table (phone keypad style)
mapping = [
    ['A', 'B', 'C'],      # 1
    ['D', 'E', 'F'],      # 2
    ['G', 'H', 'I'],      # 3
    ['J', 'K', 'L'],      # 4
    ['M', 'N', 'O'],      # 5
    ['P', 'Q', 'R'],      # 6
    ['S', 'T', 'U'],      # 7
    ['V', 'W', 'X'],      # 8
    ['Y', 'Z']            # 9
]

inp = [4, 3, 5]
res = find_combinations(inp, mapping)
print(' '.join(res))

ผลลัพธ์

JGM KGM LGM JHM KHM LHM JIM KIM LIM JGN KGN LGN JHN KHN LHN JIN KIN LIN JGO KGO LGO JHO KHO LHO JIO KIO LIO

การทำงานแบบ Step-by-Step สำหรับ [4, 3, 5]

Digit 4 (index 0): J, K, L          → out = [J, K, L]
Digit 3 (index 1): G, H, I          → out = [JG, KG, LG, JH, KH, LH, JI, KI, LI]
Digit 5 (index 2): M, N, O          → out = [JGM, KGM, LGM, JHM, KHM, LHM, ...]

# ถ้า input = [4, 3, 4] (digit 4 ซ้ำ)
# Digit 4 (index 0): J, K, L
# Digit 3 (index 1): G, H, I → JG, KG, LG, JH, KH, LH, JI, KI, LI
# Digit 4 (index 2): ต้องใช้ J/K/L เดียวกับ index 0
# → JGJ, KGK, LGL, JHJ, KHK, LHL, JIJ, KIK, LIL

เวอร์ชัน Simplified (ใช้ itertools.product)

from itertools import product

def find_combinations_simple(inp, table):
    """เวอร์ชันง่าย: ไม่ enforce consistent mapping"""
    char_lists = [table[d-1] for d in inp]
    return [''.join(p) for p in product(*char_lists)]

# Consistent mapping version
def find_combinations_consistent(inp, table):
    """Enforce same digit = same char"""
    # Group positions by digit
    from collections import defaultdict
    digit_positions = defaultdict(list)
    for i, d in enumerate(inp):
        digit_positions[d].append(i)
    
    # For each digit, choose ONE character
    unique_digits = list(digit_positions.keys())
    char_choices = [table[d-1] for d in unique_digits]
    
    results = []
    for char_combo in product(*char_choices):
        # Build string
        char_map = dict(zip(unique_digits, char_combo))
        s = ''.join(char_map[d] for d in inp)
        results.append(s)
    
    return results

Complexity

• Unique digits = u, max chars per digit = c
• Time: O(c^u × n) where n = len(inp)
• Space: O(c^u × n) for output

สรุป

• ปัญหา: Phone keypad string generation with consistent mapping
• Key constraint: Same digit → same character across all positions
• ใช้ char_map track first occurrence position
• เวอร์ชัน simplified ใช้ itertools.product + grouping