การหาระยะห่างน้อยที่สุดระหว่างสองคำในข้อความ Python

ภาพรวม

โจทย์หาจำนวนคำขั้นต่ำระหว่างคำสองคำ (word0, word1) ในข้อความ โดยวัดระยะทางเป็นจำนวนคำที่อยู่ระหว่างกัน ถ้าไม่พบคืน -1

ตัวอย่าง

ข้อความ: "cat dog abcd dog cat cat abcd dog wxyz"

word0 = "abcd", word1 = "wxyz"

ตำแหน่ง "abcd": ดัชนี 2 และ 6

ตำแหน่ง "wxyz": ดัชนี 10

ระยะห่างน้อยสุด: ระหว่างดัชนี 6 และ 10 → มีคำ "dog" 1 คำ → 1

อัลกอริทึม (Two Pointers)

แยกข้อความเป็นลิสต์คำ word_list
กำหนด ans = len(word_list) (ค่าสูงสุดเป็นไปได้)
ตัวแปร L เก็บดัชนีล่าสุดที่เจอ word0 หรือ word1
วนลูป R ทุกดัชนี:
- ถ้า word_list[R] เป็น word0 หรือ word1:
  - ถ้า L มีค่า และ word_list[R] != word_list[L] (คำต่างกัน) → อัปเดต ans = min(ans, R - L - 1)
  - อัปเดต L = R
คืน ans ถ้าเจอคู่, ไม่งั้น -1

โค้ด Python

class Solution:
    def solve(self, text, word0, word1):
        word_list = text.split()
        ans = len(word_list)
        L = None
        for R in range(len(word_list)):
            if word_list[R] == word0 or word_list[R] == word1:
                if L is not None and word_list[R] != word_list[L]:
                    ans = min(ans, R - L - 1)
                L = R
        return -1 if ans == len(word_list) else ans

ob = Solution()
text = "cat dog abcd dog cat cat abcd dog wxyz"
word0 = "abcd"
word1 = "wxyz"
print(ob.solve(text, word0, word1))

ความซับซ้อน