Interview question 17.11. word distance ●●

Interview questions 17.11. Word distance ●●

describe

There's a huge text file with words , Given any two different words , Find the shortest distance between the two words in this file ( Number of words separated ).

Advanced questions ：
If the search process is repeated many times in this file , And each time I look for a different word , Can you optimize this ?

Example

Input ：words = [“I”,“am”,“a”,“student”,“from”,“a”,“university”,“in”,“a”,“city”], word1 = “a”, word2 = “student”
Output ：1

Answer key

1. Double pointer

Create two pointers , In the process of traversing the string array , The two pointers point to the traversed range , Corresponding to the word Maximum subscript idx1 and idx2 （ That is, when the corresponding word changes the new pointer position ）, Calculate and update the interval distance every time .

• Time complexity ：O(n), among nn It's an array words The length of . You need to traverse the array for one calculation word1 and word2 The shortest distance , The time to update the subscript and the shortest distance is O(1). Here, the length of the string is regarded as a constant .
• Spatial complexity ：O(1).

class Solution {
    
public:
    int findClosest(vector<string>& words, string word1, string word2) {
    
        int idx1 = -1, idx2 = -1;
        int ans = INT_MAX;
        for(int i = 0; i < words.size(); ++i){
    
            if(words[i] == word1 || words[i] == word2){
    
                if(words[i] == word1){
                  //  Update pointer 
                    idx1 = i;
                }else{
    
                    idx2 = i;
                }
                if(idx1 >= 0 && idx2 >= 0){
             //  Update distance 
                    ans = min(ans, abs(idx1 - idx2));
                    if(ans == 1) return 1;
                }
            }
        }
        return ans;
    }
};

Advanced questions ：

If the search process is repeated many times in this file , And each time I look for a different word ,

You can maintain a Hashtable Record each word Subscript list .

Traverse the file once , Get All subscripts of each word appearing in the file .

When looking for words , Just get a list of subscripts for two words , Use Double pointer traverses two subscript linked lists , You can get the shortest distance between two words .