สมมติว่าเรามีสตริงข้อความและคำ (รายการสตริง) เราต้องหาคู่ดัชนีทั้งหมด [i, j] เพื่อให้สตริงย่อย text[i]...text [j] อยู่ในรายการคำ ดังนั้นหากสตริงเป็นเหมือน "ababa" และอาร์เรย์คำเป็นเหมือน ["aba", "ab"] ผลลัพธ์จะเป็น [[0,1], [0,2], [2,3], [2 ,4]]. สิ่งหนึ่งที่เราสังเกตได้คือไม้ขีดสามารถทับซ้อนกันได้ "aba" จะถูกจับคู่ใน [0,2] และ [2,4]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- res :=รายการว่าง
- สำหรับ i ในช่วง 0 ถึงความยาวของสตริง
- สำหรับ j ในช่วง i + 1 ถึงความยาวของสตริง + 1
- ถ้าสตริงย่อยของสตริงจากดัชนี i ถึง j ในคำ −
- เพิ่ม (i, j – 1) ลงในอาร์เรย์ผลลัพธ์
- ถ้าสตริงย่อยของสตริงจากดัชนี i ถึง j ในคำ −
- สำหรับ j ในช่วง i + 1 ถึงความยาวของสตริง + 1
- ผลตอบแทน
ตัวอย่าง(Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −
class Solution(object):
def indexPairs(self, text, words):
result = []
for i in range(len(text)):
for j in range(i+1,len(text)+1):
if text[i:j] in words:
result.append([i,j-1])
return result
ob1 = Solution()
print(ob1.indexPairs("ababa",["aba","ab"])) อินพุต
"ababa" ["aba","ab"]
ผลลัพธ์
[[0,1],[0,2],[2,3],[2,4]]
