Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.
Implement the WordDistance class:
WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict.
int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.
wordsDict[i] consists of lowercase English letters.
word1 and word2 are in wordsDict.
word1 != word2
At most 5000 calls will be made to shortest.
Solutions
Solution 1
1 2 3 4 5 6 7 8 910111213141516171819202122
classWordDistance:def__init__(self,wordsDict:List[str]):self.d=defaultdict(list)fori,winenumerate(wordsDict):self.d[w].append(i)defshortest(self,word1:str,word2:str)->int:a,b=self.d[word1],self.d[word2]ans=infi=j=0whilei<len(a)andj<len(b):ans=min(ans,abs(a[i]-b[j]))ifa[i]<=b[j]:i+=1else:j+=1returnans# Your WordDistance object will be instantiated and called as such:# obj = WordDistance(wordsDict)# param_1 = obj.shortest(word1,word2)
classWordDistance{privateMap<String,List<Integer>>d=newHashMap<>();publicWordDistance(String[]wordsDict){for(inti=0;i<wordsDict.length;++i){d.computeIfAbsent(wordsDict[i],k->newArrayList<>()).add(i);}}publicintshortest(Stringword1,Stringword2){List<Integer>a=d.get(word1),b=d.get(word2);intans=0x3f3f3f3f;inti=0,j=0;while(i<a.size()&&j<b.size()){ans=Math.min(ans,Math.abs(a.get(i)-b.get(j)));if(a.get(i)<=b.get(j)){++i;}else{++j;}}returnans;}}/** * Your WordDistance object will be instantiated and called as such: * WordDistance obj = new WordDistance(wordsDict); * int param_1 = obj.shortest(word1,word2); */
classWordDistance{public:WordDistance(vector<string>&wordsDict){for(inti=0;i<wordsDict.size();++i){d[wordsDict[i]].push_back(i);}}intshortest(stringword1,stringword2){autoa=d[word1],b=d[word2];inti=0,j=0;intans=INT_MAX;while(i<a.size()&&j<b.size()){ans=min(ans,abs(a[i]-b[j]));if(a[i]<=b[j]){++i;}else{++j;}}returnans;}private:unordered_map<string,vector<int>>d;};/** * Your WordDistance object will be instantiated and called as such: * WordDistance* obj = new WordDistance(wordsDict); * int param_1 = obj->shortest(word1,word2); */
typeWordDistancestruct{dmap[string][]int}funcConstructor(wordsDict[]string)WordDistance{d:=map[string][]int{}fori,w:=rangewordsDict{d[w]=append(d[w],i)}returnWordDistance{d}}func(this*WordDistance)Shortest(word1string,word2string)int{a,b:=this.d[word1],this.d[word2]ans:=0x3f3f3f3fi,j:=0,0fori<len(a)&&j<len(b){ans=min(ans,abs(a[i]-b[j]))ifa[i]<=b[j]{i++}else{j++}}returnans}funcabs(xint)int{ifx<0{return-x}returnx}/** * Your WordDistance object will be instantiated and called as such: * obj := Constructor(wordsDict); * param_1 := obj.Shortest(word1,word2); */