What machine learning algorithm should be used to analyze the relationship between strings?
Here is a good approach to achieve the task you want:


Step 1- Compute the Vector representation (i.e embeddings) of all the words you want to include. There are many algorithms out there to achieve this task. 



Step 2- Choose the #words corresponding to your input word (e.g dog) by applying K-Nearest Neighbors (KNN) or similar algorithms. You basically compute the distances using the embeddings.




  Steps Detailed:


Step 1- 

In NLP we represent human language as a vector of values instead of a set of characters in order to process it. To do so there are 3 approaches in the literature:

- Word Level Embeddings: Represent each word as a vector of values.
   Algorithms: Word2Vec by Google (paper), fastText by Facebook, GloVe by Stanford University (paper) ...

- Character Level Embeddings: Represent each character as a vector of values. Algorithms: ELMo (paper) ...

- Sentence Level Embeddings: Represent a sentence as a vector of values. Algorithms: Universal Sentence Encoder by Google (paper) ...

In your case I suggest to use GloVe or ElMo if you have only words and Universal Sentence Encoder if you have words and sentences.  . Compute all your words embeddings and move to the next step.

Step 2- 

Now that you have your embeddings, compute the distances between all your words (use Euclidian, Minkowski or any other distance). Notice that the computation may take some time but will only be executed once. 

Now each time you have a word (e.g dog) you apply the KNN algorithm using the computed distances and you will get the most related words to this word. 


  Note: No need to compute distances and apply KNN if you use Universal Sentence Encoder as the similarity is easily computed using a dot product of the embeddings. See my quick implementation example here for details.