c++ unordered_map solution


  • 0
    T
    class WordDistance {
        unordered_map<string, vector<int>> cache;
    public:
        WordDistance(vector<string> words) {
            for (int i = 0; i < words.size(); ++i) cache[words[i]].push_back(i);
        }
        
        int shortest(string word1, string word2) {
            int d = INT_MAX;
            for (auto i:cache[word1]) {
                for (auto j:cache[word2]) {
                    d = min(d, abs(i-j));
                }
                // another solution, use binary search to search nearest 2 indice from cache[word2], but the result didn't have obvious difference
                // auto v = cache[word2];
                // auto it = lower_bound(v.begin(), v.end(), i); it = (it ==v.end()?v.end()-1:it);
                // auto it2= (it==v.begin()?it:it-1);
                // d = min(d, min(abs(i-*it), abs(i-*it2)));
            }
            return d;
        }
    };

Log in to reply
 

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