Chương trình tính tổng các cặp chuỗi ghép nối từ danh sách trong Python

Cho một danh sách số nums. Ta cần tính tổng của mọi cặp ghép nối (concatenation) giữa hai phần tử trong danh sách. Cặp (i, j) và (j, i) được coi là khác nhau.

Ví dụ

Đầu vào: nums = [5, 3]

Các cặp ghép nối:

• 5 + 5 = 55
• 5 + 3 = 53
• 3 + 5 = 35
• 3 + 3 = 33

Tổng = 55 + 53 + 35 + 33 = 176

Thuật toán tối ưu (sử dụng memoization)

1. Tính tổng tất cả phần tử: total_sum = sum(nums).
2. Dùng dictionary memo lưu kết quả ghép nối cho mỗi giá trị duy nhất.
3. Với mỗi phần tử x trong nums:
   • Nếu x == 0: cộng total_sum vào kết quả (vì 0 concat y = y).
   • Nếu x đã có trong memo: dùng giá trị đã tính.
   • Ngược lại: tính tổng int(str(x) + str(y)) cho mọi y trong nums, lưu vào memo[x].
4. Tổng hợp kết quả.

Triển khai Python

class Solution:
    def solve(self, nums):
        memo = {}
        total_sum = sum(nums)
        n = len(nums)
        result = 0
        for x in nums:
            if x == 0:
                result += total_sum
            else:
                if x in memo:
                    result += memo[x]
                else:
                    concat_sum = 0
                    for y in nums:
                        concat_sum += int(str(x) + str(y))
                    memo[x] = concat_sum
                    result += concat_sum
        return result

# Test
ob = Solution()
print(ob.solve([5, 3]))  # Output: 176

Độ phức tạp

• Thời gian: O(n²) trong trường hợp xấu nhất, nhưng memoization giúp giảm thiểu khi có nhiều giá trị trùng lặp.
• Không gian: O(k) với k là số giá trị duy nhất trong nums.