โปรแกรม Python ตรวจสอบการสร้าง Array จาก Pieces (Concatenation)

กำหนด Array nums (Unique Elements) และ Array ของ Sub-arrays pieces ตรวจสอบว่าสามารถ Concatenate pieces ในบางลำดับ ได้ nums หรือไม่ ห้ามเรียงลำดับใหม่ภายในแต่ละ piece

ตัวอย่าง

• Input: nums = [5,1,12,36,2,47,6], pieces = [[2,47,6],[12,36],[1],[5]]
• Output: True

Concatenation Order: [5] + [1] + [12,36] + [2,47,6] = [5,1,12,36,2,47,6] ✓

อัลกอริธึม: Hash Map + Linear Scan

1. สร้าง Map: first_element → piece จาก pieces
2. Scan nums จากซ้ายไปขวา:
   • ดู Element ปัจจุบัน หาใน Map
   • ถ้าไม่เจอ → False
   • ถ้าเจอ → ตรวจสอบว่า Subarray ถัดไปใน nums ตรงกับ Piece นั้นหมดหรือไม่
   • ข้าม Index ตามความยาว Piece
3. ถ้าจบ Loop ได้ → True

โค้ด Python

def can_form_array(nums, pieces):
    """
    ตรวจสอบว่าสามารถสร้าง nums จาก pieces ได้หรือไม่
    
    Args:
        nums: List[int] - Array เป้าหมาย (Unique Elements)
        pieces: List[List[int]] - Array ของ Sub-arrays
    
    Returns:
        bool
    """
    # สร้าง Map: First Element -> Piece
    piece_map = {piece[0]: piece for piece in pieces}
    
    i = 0
    while i < len(nums):
        if nums[i] not in piece_map:
            return False
        
        piece = piece_map[nums[i]]
        piece_len = len(piece)
        
        # ตรวจสอบว่า Subarray ตรงกับ Piece หรือไม่
        if nums[i:i + piece_len] != piece:
            return False
        
        i += piece_len  # ข้ามไปยัง Element ถัดไปหลัง Piece
    
    return True


# ทดสอบ
if __name__ == "__main__":
    # Test Case 1
    nums = [5, 1, 12, 36, 2, 47, 6]
    pieces = [[2, 47, 6], [12, 36], [1], [5]]
    print(f"Test 1: {can_form_array(nums, pieces)}")  # True

    # Test Case 2: Order matters within piece
    nums = [1, 2, 3]
    pieces = [[1, 3], [2]]
    print(f"Test 2: {can_form_array(nums, pieces)}")  # False (1,3 ไม่ใช่ 1,2)

    # Test Case 3: Missing element
    nums = [1, 2, 3]
    pieces = [[1], [2]]
    print(f"Test 3: {can_form_array(nums, pieces)}")  # False (missing 3)

    # Test Case 4: Extra piece
    nums = [1, 2]
    pieces = [[1], [2], [3]]
    print(f"Test 4: {can_form_array(nums, pieces)}")  # False (extra piece not used)

    # Test Case 5: Single element
    nums = [42]
    pieces = [[42]]
    print(f"Test 5: {can_form_array(nums, pieces)}")  # True

ผลลัพธ์

Test 1: True
Test 2: False
Test 3: False
Test 4: False
Test 5: True

Complexity Analysis

• Time: O(n + m) โดย n = len(nums), m = total elements in pieces
• Space: O(m) สำหรับ Hash Map

ข้อสังเกตสำคัญ

• nums มี Unique Elements → Element แรกของแต่ละ Piece เป็น Unique Key ได้
• ไม่ต้อง Permute Pieces เพราะ Map บอกลำดับโดยอัตโนมัติจาก nums
• ตรวจสอบ Subarray ด้วย Slice nums[i:i+len] เร็วและอ่านง่าย

LeetCode Reference

Problem 1640: "Check Array Formation Through Concatenation" - Easy