ระยะทางสั้นที่สุดระหว่างคำ II ใน C++

สมมติว่ามีคลาสที่รับรายการคำในคอนสตรัคเตอร์ มีเมธอดที่รับ word1 และ word2 เพื่อหาระยะทางสั้นที่สุด เมธอดนี้จะถูกเรียกหลายครั้งกับพารามิเตอร์ที่ต่างกัน

ตัวอย่าง: words = ["practice", "makes", "perfect", "skill", "makes"], word1 = "skill", word2 = "practice" ผลลัพธ์ = 3

วิธีแก้ปัญหา

1. ในคอนสตรัคเตอร์: สร้าง map เก็บตำแหน่งของแต่ละคำ
2. ในเมธอด shortest():
   • ดึงอาร์เรย์ตำแหน่งของ word1 และ word2
   • ใช้ two-pointer เดินหาความต่างน้อยที่สุด
   • เวลา O(|arr1| + |arr2|) ต่อการเรียก

ตัวอย่างโค้ด C++

#include <bits/stdc++.h> 
using namespace std; 

class WordDistance { 
public: 
    unordered_map<string, vector<int> > m; 
    WordDistance(vector<string>& words) { 
        for(int i = 0; i < words.size(); i++){ 
            m[words[i]].push_back(i); 
        } 
    } 
    int shortest(string word1, string word2) { 
        vector<int>& arr1 = m[word1]; 
        vector<int>& arr2 = m[word2]; 
        int i = 0, j = 0; 
        int ret = INT_MAX; 
        while (i < arr1.size() && j < arr2.size()) { 
            ret = min(ret, abs(arr1[i] - arr2[j])); 
            if (arr1[i] < arr2[j]) i++; 
            else j++; 
        } 
        return ret; 
    } 
}; 

int main(){ 
    vector<string> v = {"practice", "makes", "perfect", "skill","makes"}; 
    WordDistance ob(v); 
    cout << (ob.shortest("skill", "practice")) << endl; 
    cout << (ob.shortest("makes", "skill")); 
}

ข้อมูลนำเข้า

{"practice", "makes", "perfect", "skill", "makes"} Call shortest("skill", "practice") Call shortest("makes", "skill")

ผลลัพธ์

3 1