Shortest Word Distance Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon Goldman Sachs Google LinkedIn Microsoft Salesforce Uber
Array StringViews 3091

Problem Statement

The Shortest Word Distance LeetCode Solution – says that you’re given an array of strings and two different words. We need to return the shortest distance between these two words that appear in the input string.Shortest Word Distance Leetcode Solution

Example:

Input:  wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

Explanation:

  • Word “coding” occurs at position 4.
  • Word “practice” occurs at position 1.
  • The shortest distance is 3.
Input:  wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

Explanation:

  • Word “coding” occurs at position 4.
  • Word “makes” occurs at positions 2 and 5.
  • Shortest distance is 5-4 = 1.

Approach

This is a straight-forward coding problem. The distance between any two positions i_1 and i_2 in an array is |i_1 – i_2|. To find the shortest distance between word1 and word2, we need to traverse the input array and find all occurrences i_1 and i_2 of the two words, and check if |i_1 – i_2| is less than the minimum distance computed so far.

Idea:

  1. Maintain two position variables for each word.
  2. Iterate in the string array and update two position variables accordingly.
  3. Our Answer is the minimum absolute difference between these position variables.

Code

C++ Solution:

class Solution {
public:
    int shortestDistance(vector<string>& wordsDict, string word1, string word2) {
        int ans = INT_MAX,pos1 = -1,pos2 = -1;
        for(int i=0;i<wordsDict.size();i++){
            if(wordsDict[i]==word1){
                pos1 = i;
            }
            if(wordsDict[i]==word2){
                pos2 = i;
            }
            if(pos1!=-1 and pos2!=-1){
                ans = min(ans,abs(pos1-pos2));
            }
        }
        return ans;
    }
};

Java Solution:

class Solution {
    public int shortestDistance(String[] wordsDict, String word1, String word2) {
        int ans = Integer.MAX_VALUE,pos1 = -1,pos2 = -1;
        for(int i=0;i<wordsDict.length;i++){
            if(wordsDict[i].equals(word1)){
                pos1 = i;
            }
            if(wordsDict[i].equals(word2)){
                pos2 = i;
            }
            if(pos1!=-1 && pos2!=-1){
                ans = Math.min(ans,Math.abs(pos1-pos2));
            }
        }
        return ans;
    }
}

Complexity Analysis for Shortest Word Distance Leetcode Solution

Time Complexity

The time complexity of the above code is O(N) since we’re iterating over the entire input string exactly once.

Space Complexity

The space complexity of the above code is O(1) since we’re using only constant space.

Reference: https://en.wikipedia.org/wiki/One-pass_algorithm

Translate »