วิธีตรวจสอบว่าความถี่ตัวอักษรเป็นลำดับ Recaman Series ใน Python

ปัญหา

กำหนดสตริงตัวพิมพ์เล็ก s ตรวจสอบว่าความถี่ของตัวอักษร (จัดเรียงใหม่ได้) ตรงกับลำดับ Recaman (ไม่นับพจน์แรก 0) หรือไม่

ลำดับ Recaman: 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, ...

ตัวอย่าง: "pppuvuuqquuu" → ความถี่ p:3, u:6, v:1, q:2 → ตรง [1,3,6,2] → True

แนวทางแก้ปัญหา

1. นับความถี่ตัวอักษร (freq)
2. สร้างลำดับ Recaman จำนวน n พจน์ (n = จำนวนตัวอักษรที่ไม่ซ้ำ)
3. ตรวจสอบว่าความถี่ทุกตัวมีอยู่ในลำดับ Recaman

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

from collections import defaultdict

def recaman(array, n):
    array[0] = 0
    for i in range(1, n + 1):
        temp = array[i - 1] - i
        for j in range(i):
            if array[j] == temp or temp < 0:
                temp = array[i - 1] + i
                break
        array[i] = temp

def solve(s):
    freq = defaultdict(int)
    for ch in s:
        freq[ch] += 1
    n = len(freq)
    array = [0] * (n + 1)
    recaman(array, n)
    f = 1
    for key in freq.keys():
        is_found = 0
        for j in range(1, n + 1):
            if freq[key] == array[j]:
                is_found = 1
                break
        if not is_found:
            f = 0
            break
    return True if f else False

s = "pppuvuuqquuu"
print(solve(s))  # True

อินพุต / เอาต์พุต

Input: "pppuvuuqquuu"
Output: True