[20.5] Find the sortest distance between two words in the file

1. Example

"I am so awesome,so awesome, so awesome, so cool , so .."
so awesome = > 0 ! shortest
so "..." awesome => 4

Searching operation in O(1) ? Space Complexity?


2. Implementation
Q1: find the two word,  outer inward?
A1: frist last first = word1and last = word2
Q1: does word order matter word1,-word2 or word2- word1 counts?
A1: consider order doesn't matter here

public int shortest(String[] words, String word1, String word2)
{



        int min = Integer.MAX_VALUE;
        int word1_pos = -min;     // since word1_pos - word2_pos if word1_pos has value
        int word2_pos = -min;


        // validate the input
        if ( words == null || word1 == null || word2 == null )
          return min;


 


        for (int i = 0; i < words.length; i++)
        {
               String current_word = words[i];
               if (current_word.equals(word1))
               {
                      word1_pos = i;
                      int distance = word1_pos - word2_pos;
                      if (min > distance)
                          min = distance;
               }
               else if ( current_word.equals(word2))
               {
                      word2_pos = i;
                      int distance = word2_pos - word1_pos;
                      if (min > distance)
                          min = distance;
               }

      
        }


      
       return min;

 

}

To solve this problem in less time (But more space), we can create a hash table with each word and the locations where it occurs.
We then just need to find the minimum (arithmetic) difference in the locations (e.g., abs(   word0.loc[1] - word1.loc[5]  ))


To find the minimum arithmetic difference, we take each location for word1,e.g., {0,3} and do a modified binary search for it in word2's location list, return the closest number. our search for 3, for example, in {2,7,9} would return 1. The minimum of all these binary searches is the shortest distance.

http://weihungleetcodearray.blogspot.com/2015/08/searchbinary-search-search-insert.html

3 .Similar Ones