ตรวจสอบว่า 1 ในสตริงไบนารีมีระยะห่างเท่ากันทุกคู่หรือไม่ใน Python

ภาพรวม

บทความนี้ตรวจสอบว่าในสตริงไบนารี ตัว 1 ทุกตัวมีระยะห่างเท่ากันหรือไม่ (equidistant) โดยสตริงต้องมี 1 อย่างน้อย 2 ตัว

อัลกอริทึม

1. เก็บดัชนีของทุกตัว 1 ไว้ในลิสต์ index
2. คำนวณระยะห่างระหว่าง 1 ตัวแรกและตัวที่สอง (index[1] - index[0])
3. ตรวจสอบว่าระยะห่างระหว่าง 1 ทุกคู่ที่ติดกัน เท่ากับระยะห่างแรกหรือไม่

ตัวอย่างโค้ด Python

def solve(s):
    index = []
    for i in range(len(s)):
        if s[i] == '1':
            index.append(i)
    t = len(index)
    for i in range(1, t):
        if (index[i] - index[i - 1]) != (index[1] - index[0]):
            return False
    return True

s = "100001000010000"
print(solve(s))  # True (ระยะห่าง 4)

ผลลัพธ์

True

คำอธิบายเพิ่มเติม

ตัวอย่าง "100001000010000" มี 1 อยู่ที่ดัชนี 0, 5, 10, 15 ระยะห่างแต่ละคู่คือ 5 (แต่โค้ดนับดัชนีจาก 0 ดังนั้นความต่างคือ 5) โค้ดตรวจสอบได้ใน O(n)