ตรวจสอบว่าสตริงมีความถี่ตัวอักษรเท่ากันทุกตัวโดยอนุญาตให้แตกต่าง 1 ตัวใน Python

สมมติว่าเรามีสตริงพิมพ์เล็ก s เราต้องตรวจสอบว่าสามารถแปลง s เป็นสตริงที่ถูกต้องได้โดยการลบสูงสุด 1 ตัวอักษร สตริงที่ถูกต้องหมายถึงสตริง str ที่สำหรับตัวอักษรที่ไม่ซ้ำกันใน str ทุกตัวมีความถี่เท่ากัน

เช่น ถ้าอินพุตเป็น s = "xyyzx" ผลลัพธ์จะเป็น True เนื่องจากเราสามารถลบ z แล้วสตริงจะเป็น "xyyx" ซึ่ง x และ y มีความถี่เท่ากัน

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:

• size := 26
• occurrence := อาร์เรย์ขนาด 26 เก็บความถี่ของแต่ละตัวอักษรใน s
• occr1 := 0, occr1_cnt := 0
• สำหรับ i ในช่วง 0 ถึง size - 1 ทำ
  • ถ้า occurrence[i] ไม่ใช่ 0 แล้ว
    • occr1 := occurrence[i], occr1_cnt := 1, ออกจากลูป
• occr2 := 0, occr2_cnt := 0
• สำหรับ j ในช่วง i+1 ถึง size - 1 ทำ
  • ถ้า occurrence[j] ไม่ใช่ 0 แล้ว
    • ถ้า occurrence[j] เท่ากับ occr1 แล้ว
      • occr1_cnt := occr1_cnt + 1
    • มิฉะนั้น
      • occr2_cnt := 1, occr := occurrence[j], ออกจากลูป
• สำหรับ k ในช่วง j+1 ถึง size - 1 ทำ
  • ถ้า occurrence[k] ไม่ใช่ 0 แล้ว
    • ถ้า occurrence[k] เท่ากับ occr1 แล้ว
      • occr1_cnt := occr1_cnt + 1
    • ถ้า occurrence[k] เท่ากับ occr2 แล้ว
      • occr2_cnt := occr2_cnt + 1
    • มิฉะนั้น
      • คืนค่า False
  • ถ้า occr1_cnt > 1 และ occr2_cnt > 1 แล้ว
    • คืนค่า False
• คืนค่า True

ลองดูการนำไปใช้ดังต่อไปนี้เพื่อเข้าใจได้ดียิ่งขึ้น:

ตัวอย่าง

size = 26
def solve(str):
    occurrence = [0]*size
    for i in range(len(str)):
        occurrence[ord(str[i])-ord('a')] += 1
    occr1 = 0
    occr1_cnt = 0
    for i in range(size):
        if (occurrence[i] != 0):
            occr1 = occurrence[i]
            occr1_cnt = 1
            break
    occr2 = 0
    occr2_cnt = 0
    for j in range(i+1, size):
        if (occurrence[j] != 0):
            if (occurrence[j] == occr1):
                occr1_cnt += 1
            else:
                occr2_cnt = 1
                occr = occurrence[j]
                break
    for k in range(j+1, size):
        if occurrence[k] != 0:
            if (occurrence[k] == occr1):
                occr1_cnt += 1
            if (occurrence[k] == occr2):
                occr2_cnt += 1
            else:
                return False
    if occr1_cnt > 1 and occr2_cnt > 1:
        return False
    return True

s = "xyyzx"
print(solve(s))

อินพุต

"xyyzx"

ผลลัพธ์

True