โปรแกรมนับจำนวนสตริงย่อยที่แตกต่างกันในสตริงที่กำหนดด้วย Python

สมมติว่าเราได้รับสตริงย่อยที่แทนด้วย 's' เราต้องหาสตริงย่อยที่ไม่ซ้ำกันและส่งคืนจำนวนของสตริงย่อยเหล่านี้เป็นผลลัพธ์

เช่น ถ้าอินพุตคือ s = 'prrstvt' ผลลัพธ์จะเป็น 26 สตริงย่อยที่แตกต่างกันจะเป็น: 'pr', 'rrs', 'st', 'rr', 'tv', 'rstv', 'stvt', 'prrstv', 'prrstvt', 'rrstvt', 's', 'prrst', 'stv', 'rrstv', 'rst', 'v', 'tvt', 'rstvt', 'r', 'rs', 'vt', 't', 'prr', 'p', 'rrst', และ 'prrs'

วิธีแก้ปัญหา

• visited := แมปใหม่
• สำหรับแต่ละดัชนี ind และค่า let ใน s:
  • temp := เซตใหม่
  • ถ้า ind-1 อยู่ใน visited:
    • สำหรับแต่ละ has_let ใน visited[ind-1]: เพิ่ม (has_let + let) ลง temp
  • เพิ่ม let ลง temp
  • visited[ind] := temp
• res := เซตใหม่
• สำหรับแต่ละ sets ใน visited: เพิ่ม visited[sets] ลง res
• return ขนาดของ res

ตัวอย่าง

def solve(s):
    visited = dict()
    for ind, let in enumerate(s):
        temp = set()
        if ind-1 in visited:
            for has_let in visited[ind-1]:
                temp.add(has_let+let)
        temp.add(let)
        visited[ind] = temp
    res = set()
    for sets in visited:
        res.update(visited[sets])
    return len(res)

print(solve('prrstvt'))

อินพุต

'prrstvt'

เอาต์พุต

26