ภาพรวม
บทความนี้อธิบายวิธีตรวจสอบว่า "การเข้ารหัส" (encoding) ที่กำหนด สามารถระบุสตริงไบนารีที่มีความยาว k ได้อย่างเดียว (uniquely) หรือไม่ การเข้ารหัสเก็บจำนวนของ 1 ที่ติดกัน (contiguous 1s) ซึ่งคั่นด้วย 0 เดียว
ตัวอย่าง
encoding = [4, 2, 3] หมายถึง สตริงไบนารี: 1111 0 11 0 111 = 11110110111 (ความยาว 11)
เงื่อนไขความเป็นเอกลักษณ์
การเข้ารหัสระบุสตริงได้อย่างเดียว ก็ต่อเมื่อ ผลรวมของจำนวน 1 ทั้งหมด + (จำนวนกลุ่ม - 1) เท่ากับความยาว k ที่กำหนด
สูตร: sum(nums) + len(nums) - 1 == k
ตัวอย่างโค้ด Python
def solve(nums, k):
total = sum(nums)
total += len(nums) - 1
return total == k
nums = [4, 2, 3]
k = 11
print(solve(nums, k)) # True
ผลลัพธ์
True
คำอธิบายเพิ่มเติม
หากผลรวมไม่เท่ากับ k แสดงว่าการเข้ารหัสไม่สอดคล้องกับความยาวที่กำหนด อาจมีช่องว่างหรือ 0 เพิ่มเติม ทำให้ไม่สามารถระบุสตริงได้อย่างเดียว
