สมมติว่าเรามีสตริง s และสตริง t อีกอัน และ t เป็นผลสืบเนื่องของ s เราต้องหาความยาวสูงสุดของสตริงย่อยที่เราสามารถลบออกจาก s ได้ เพื่อที่ t จะยังคงเป็นผลสืบเนื่องของ s
ดังนั้น หากอินพุตเป็น s ="xyzxyxz" t ="yz" ผลลัพธ์จะเป็น 4 เนื่องจากเราสามารถลบสตริงย่อย "abca"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ซ้าย :=รายการใหม่ ขวา :=รายการใหม่ด้วย
-
c1 :=-1, c2 :=-1, c3 :=-1
-
เจ :=0
-
สำหรับฉันในช่วง 0 ถึงขนาด s ทำ
-
ถ้า s[i] เหมือนกับ t[j] แล้ว
-
ใส่ i ที่ท้ายด้านซ้าย
-
เจ :=เจ + 1
-
-
ถ้า j เท่ากับขนาดของ t แล้ว
-
c1 :=ขนาดของ s - i - 1
-
ออกจากวง
-
-
-
j :=ขนาด t - 1
-
สำหรับฉันในช่วงขนาด s - 1 ถึง 0, ลดลง 1 ทำ
-
ถ้า s[i] เหมือนกับ t[j] แล้ว
-
แทรก i เข้าไปทางขวาที่ตำแหน่ง 0
-
เจ :=เจ - 1
-
-
ถ้า j เหมือนกับ -1 แล้ว
-
c2 :=ฉัน
-
ออกจากวง
-
-
-
สำหรับฉันในช่วง 0 ถึงขนาดของ t - 1 ทำ
-
c3 :=สูงสุดของ c3 และ (right[i + 1] - left[i] - 1)
-
-
ส่งกลับสูงสุด c1, c2 และ c3
ตัวอย่าง (Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution: def solve(self, s, t): left = [] right = [] c1 = -1 c2 = -1 c3 = -1 j = 0 for i in range(len(s)): if s[i] == t[j]: left.append(i) j += 1 if j == len(t): c1 = len(s) - i - 1 break j = len(t) - 1 for i in range(len(s) - 1, -1, -1): if s[i] == t[j]: right.insert(0, i) j -= 1 if j == -1: c2 = i break for i in range(len(t) - 1): c3 = max(c3, right[i + 1] - left[i] - 1) return max(c1, c2, c3) ob = Solution() s = "xyzxyxz" t = "yz" print(ob.solve(s, t))
อินพุต
"xyzxyxz", "yz"
ผลลัพธ์
4
