Chương trình kiểm tra có thể đứng cách ít nhất k khỏi người gần nhất trong Python

Cho chuỗi s và số k. Ký tự '.' là chỗ trống, 'x' là người. Kiểm tra có thể chọn vị trí đứng sao cho khoảng cách đến người gần nhất >= k (khoảng cách giữa chỉ số liền kề là 1).

Ví dụ, s = "x...x..", k = 2, đầu ra True (có thể đứng ở chỉ số 2 hoặc 6).

Các bước giải quyết:

• pos := vị trí đầu tiên của 'x' (hoặc -1 nếu không có).
• Nếu pos == -1 hoặc pos >= k, trả về True.
• last_x := pos, dist_min := 2*k - 1.
• Lặp vô hạn:
  • next_x := vị trí 'x' tiếp theo từ last_x+1 (hoặc -1).
  • Nếu next_x != -1:
    • Nếu next_x - last_x - 1 >= dist_min, trả về True.
    • last_x = next_x.
  • Ngược lại:
    • Nếu len(s) - last_x - 1 >= k, trả về True.
    • Ngược lại trả về False.
• Trả về None (không bao giờ đạt).

Ví dụ minh họa

class Solution:
    def solve(self, s, k):
        pos = s.find("x")
        if pos == -1 or pos >= k:
            return True
        last_x = pos
        dist_min = 2 * k - 1
        while True:
            next_x = s.find("x", last_x + 1)
            if next_x != -1:
                if next_x - last_x - 1 >= dist_min:
                    return True
                last_x = next_x
            else:
                if len(s) - last_x - 1 >= k:
                    return True
                return False
        return None

ob = Solution()
print(ob.solve("x...x..", 2))

Đầu vào

"x...x..", 2

Đầu ra

True