Các cặp chỉ số của chuỗi (Index Pairs of a String) trong Python

Cho chuỗi text và danh sách words, cần tìm tất cả cặp chỉ số [i, j] sao cho chuỗi con text[i]...text[j] nằm trong danh sách words. Ví dụ: text="ababa", words=["aba", "ab"] cho kết quả [[0,1], [0,2], [2,3], [2,4]]. Lưu ý: các khớp có thể chồng chéo, "aba" khớp tại [0,2] và [2,4].

Để giải quyết:

• res := list rỗng
• Với i từ 0 đến độ dài chuỗi:
  • Với j từ i+1 đến độ dài chuỗi + 1:
    • Nếu chuỗi con từ i đến j có trong words: thêm (i, j-1) vào kết quả
• Trả về kết quả

Ví dụ (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"]))

Đầu vào

"ababa" ["aba", "ab"]

Kết quả

[[0, 1], [0, 2], [2, 3], [2, 4]]