C# - Hash list of indexes, use 2 pointer search to find min


  • 0

    Make a hash for each word to a list of indexes for that word, store this result. To find min distance use 2 pointers for each of the lists for the given words. Advance the pointer for the smaller value. If you find 1 you can terminate or if the smaller pointer is already at the end of the list you can terminate.

        Dictionary<string,List<int>> map;
        
        public WordDistance(string[] words) 
        {
            this.map = new Dictionary<string,List<int>>();
            for (int i = 0; i < words.Length; i++)
            {
                if (!map.ContainsKey(words[i])) map[words[i]] = new List<int>();
                map[words[i]].Add(i);
            }
        }
    
        public int Shortest(string word1, string word2) 
        {
            List<int> list1 = this.map[word1];
            List<int> list2 = this.map[word2];
            
            int index1 = 0;
            int index2 = 0;
            int min = int.MaxValue;
            while (true)
            {
                min = Math.Min(min, Math.Abs(list1[index1] - list2[index2]));
                
                if (min == 1) break;
                else if (index1 < list1.Count - 1 && list1[index1] < list2[index2]) index1++;
                else if (index2 < list2.Count - 1 && list2[index2] < list1[index1]) index2++;
                else break;
            }
            return min;
        }
    

  • 0

    Thank you for sharing. A suggestion on while(true) with break pattern, since it requires more care to prevent an infinite loop.

        public int Shortest(string word1, string word2) {
                List<int> list1 = this.dict[word1];
                List<int> list2 = this.dict[word2];
    
                int index1 = 0;
                int index2 = 0;
                int min = int.MaxValue;
    
                while (index1 < list1.Count && index2 < list2.Count)
                {
                    min = Math.Min(min, Math.Abs(list1[index1] - list2[index2]));
                    if (list1[index1] < list2[index2])
                    {
                        index1++;
                    }
                    else
                    {
                        index2++;
                    }
                }
    
                return min;
        }
    

Log in to reply
 

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