One pass clean O(1) space 29ms C++ solution


  • 0
    V

    The idea here is that we consider w1 - w2 pair only in range which can improve the ans. So for next occurance of w1(indicated by w1i), we set w2i prior to w1i at distance of current ans.

    class Solution {
    public:
        int shortestDistance(vector<string>& w, string w1, string w2) {
            int w1i = 0, w2i = 0, n = w.size(), ans = n;
                
            while (w1i < n) {
                while (w1i < n && w[w1i] != w1)
                    w1i++;
                if (w1i == n)
                    return ans;
                w2i = (w1i - ans + 1) >= 0 ? (w1i - ans + 1) : 0; // this is best w2i ~ w1i can improve
                while (w2i < n && abs(w2i - w1i) <= ans) {
                    if (w[w2i] == w2)
                        ans = min(ans, abs(w2i - w1i));
                    w2i++;
                }
                w1i++;
            }
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.