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

Cho một mảng các từ words và hai từ word1, word2 (có thể trùng nhau). Tìm khoảng cách ngắn nhất giữa hai từ này trong mảng. Hai từ đại diện cho hai vị trí riêng biệt (ngay cả khi chúng giống nhau).

Ví dụ

Đầu vào: words = ["practice", "makes", "perfect", "skill", "makes"], word1 = "makes", word2 = "skill"
Đầu ra: 1 (vị trí 3 và 4).

Thuật toán quét một lần (One-pass)

Duy trì hai biến last1, last2 lưu vị trí gần nhất của word1 và word2. Khi gặp từ khớp:

• Nếu word1 == word2: cập nhật last1 = last2 trước, sau đó last2 = i (đảm bảo hai vị trí khác nhau).
• Nếu khác nhau: cập nhật biến tương ứng.
• Mỗi bước cập nhật kết quả ans = min(ans, abs(last1 - last2)).

Triển khai C++

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

class Solution {
public:
    int shortestWordDistance(vector<string>& words, string word1, string word2) {
        int ans = INT_MAX;
        int last1 = INT_MAX, last2 = INT_MIN;
        for (int i = 0; i < words.size(); ++i) {
            if (words[i] == word1) last1 = i;
            if (words[i] == word2) {
                if (word1 == word2) last1 = last2;
                last2 = i;
            }
            if (last1 != INT_MAX && last2 != INT_MIN)
                ans = min(ans, abs(last1 - last2));
        }
        return ans;
    }
};

Độ phức tạp

• Thời gian: O(N) - duyệt mảng một lần.
• Không gian: O(1) - chỉ dùng vài biến phụ.

Kết quả kiểm thử

Đầu vào: {"practice", "makes", "perfect", "skill", "makes"}, "makes", "skill"
Đầu ra: 1