สมมติว่าเรามีสตริง เราต้องหาจำนวนสูงสุดของสตริงย่อยเฉพาะที่สามารถแยกสตริงที่กำหนดได้ เราสามารถแยกสตริงออกเป็นรายการของสตริงย่อยที่ไม่ว่างเปล่า เพื่อให้การต่อกันของสตริงย่อยเป็นสตริงดั้งเดิม แต่เราต้องแยกสตริงย่อยออกเพื่อให้ทั้งหมดเหมือนกัน
ดังนั้น หากอินพุตเป็น s ="pqpqrrr" ผลลัพธ์จะเป็น 5 เพราะเราสามารถแยกออกเป็น ['p', 'q', 'pq', 'r', 'rr'] ถ้าเราแยกเช่น ['p', 'q', 'p', 'q', 'r', 'rr'] ไม่ถูกต้องเพราะที่นี่ 'p' และ 'q' ปรากฏหลายครั้ง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- res :=รายการที่มีองค์ประกอบเดียว 0
- กำหนดฟังก์ชัน dfs() นี่จะใช้เวลา s, เส้นทางซึ่งเป็นชุดว่างใหม่
- ถ้า s ว่าง ก็
- res[0] :=สูงสุดของ res[0] และขนาดของเส้นทาง
- คืนสินค้า
- สำหรับฉันในช่วง 1 ถึงขนาด s ทำ
- x :=subarray ของ s[จากดัชนี 0 ถึง i-1]
- ถ้า x ไม่อยู่ในเส้นทางแล้ว
- dfs(สตริงย่อยของ s[จากดัชนี i ถึง end], เส้นทาง U {x})
- จากวิธีหลัก ให้ทำดังนี้ -
- dfs
- ผลตอบแทน[0]
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(s):
res = [0]
def dfs(s, path=set()):
if not s:
res[0] = max(res[0], len(path))
return
for i in range(1, len(s)+1):
x = s[:i]
if x not in path:
dfs(s[i:], path|{x})
dfs(s)
return res[0]
s = "pqpqrrr"
print(solve(s)) อินพุต
"pqpqrrr"
ผลลัพธ์
5
