NUHMAN.com

🔍 Problem Statement

Given two words word1 and word2 and a list of words words, find the shortest distance between the two words in the list.

You may assume that word1 and word2 do not appear at the same index in the list.

🧠 Approach

We need to find the minimum distance between the indices of two words (word1 and word2) in the list of words. Here's a simple approach:

1. Two Pointers Approach:

• Maintain two pointers (index1 and index2) to store the indices of word1 and word2.
• Traverse the list once. If the current word is word1, update index1. Similarly, if the current word is word2, update index2.
• Every time we update one of the indices, check the absolute difference between index1 and index2. If it's smaller than the current minimum distance, update the minimum distance.

1. Edge Case: Since both words are guaranteed to exist in the list, there's no need to handle cases where one of the words is missing.

Steps:

1. Initialize index1 and index2 to -1.
2. Traverse through the list of words.
3. Update index1 and index2 when we encounter word1 and word2.
4. Keep track of the minimum distance between index1 and index2.

✅ Go Implementation

go

package main

import (
	"fmt"
	"math"
)

// Function to find the shortest distance between two words
func shortestDistance(words []string, word1 string, word2 string) int {
	// Initialize the indices of word1 and word2
	index1, index2 := -1, -1
	minDistance := math.MaxInt32 // Set to the largest possible integer value

	// Loop through the words list
	for i, word := range words {
		if word == word1 {
			index1 = i
		} else if word == word2 {
			index2 = i
		}

		// If both words have been found, calculate the distance
		if index1 != -1 && index2 != -1 {
			distance := abs(index1 - index2)
			if distance < minDistance {
				minDistance = distance
			}
		}
	}

	return minDistance
}

// Function to compute the absolute value
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

// Test the shortestDistance function
func main() {
	// Example 1: "practice" and "makes"
	words1 := []string{"practice", "makes", "perfect", "practice", "makes"}
	word1_1, word2_1 := "practice", "makes"
	fmt.Println(shortestDistance(words1, word1_1, word2_1)) // Output: 1

	// Example 2: "hello" and "world"
	words2 := []string{"hello", "world", "hello", "world"}
	word1_2, word2_2 := "hello", "world"
	fmt.Println(shortestDistance(words2, word1_2, word2_2)) // Output: 1
}

🧑‍💻 Explanation of the Code

1. shortestDistance function:

• Step 1: We initialize index1 and index2 to -1, and minDistance to the largest possible integer value (math.MaxInt32), which will keep track of the minimum distance.
• Step 2: We iterate through the words list. If the current word is word1, we update index1, and if it’s word2, we update index2.
• Step 3: Every time both index1 and index2 are updated, we calculate the absolute difference between the two indices and compare it with the current minDistance. If it's smaller, we update the minimum distance.
• Step 4: After the loop finishes, we return minDistance, which will be the shortest distance between word1 and word2 in the list.

1. abs function:

• This is a helper function to compute the absolute value of an integer.

1. main function:

• We run the shortestDistance function on two examples, one with the words "practice" and "makes", and another with "hello" and "world", and print the results.

📦 Example Usage

go

func main() {
	// Example 1: "practice" and "makes"
	words1 := []string{"practice", "makes", "perfect", "practice", "makes"}
	word1_1, word2_1 := "practice", "makes"
	fmt.Println(shortestDistance(words1, word1_1, word2_1)) // Output: 1

	// Example 2: "hello" and "world"
	words2 := []string{"hello", "world", "hello", "world"}
	word1_2, word2_2 := "hello", "world"
	fmt.Println(shortestDistance(words2, word1_2, word2_2)) // Output: 1
}

Example Output:

1
1

⏱️ Time & Space Complexity

• Time Complexity: The time complexity is O(n), where n is the number of words in the words list. We are iterating through the list once.
• Space Complexity: The space complexity is O(1) since we are only using a few integer variables to store indices and the minimum distance.

This solution efficiently solves the problem with linear time complexity.