Khoảng cách từ ngắn nhất II (Shortest Word Distance II) trong C++

Thiết kế lớp WordDistance nhận một mảng từ trong constructor. Phương thức shortest(word1, word2) được gọi nhiều lần với các tham số khác nhau, cần trả về khoảng cách ngắn nhất giữa hai từ. Tối ưu cho nhiều truy vấn.

Ví dụ

Đầu vào: words = ["practice", "makes", "perfect", "skill", "makes"]
shortest("skill", "practice") → 3
shortest("makes", "skill") → 1

Thuật toán tiền xử lý + hai con trỏ

1. Constructor: Xây dựng unordered_map<string, vector<int>> ánh xạ từ → danh sách chỉ số (đã sắp xếp tự nhiên do duyệt tuần tự).
2. shortest(): Lấy hai mảng chỉ số arr1, arr2. Sử dụng hai con trỏ i, j duyệt cùng lúc:
   • Cập nhật ans = min(ans, abs(arr1[i] - arr2[j])).
   • Tăng con trỏ trỏ đến chỉ số nhỏ hơn (để thu hẹp khoảng cách).

Triển khai C++

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

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

Độ phức tạp

• Constructor: O(N) thời gian, O(N) không gian.
• shortest(): O(|A| + |B|) thời gian, O(1) không gian thêm.

Kết quả kiểm thử

Đầu vào: {"practice","makes","perfect","skill","makes"} gọi shortest("skill","practice") và shortest("makes","skill")
Đầu ra: 3 1