FastPrepShortest Word Chain Between Two Words

Shortest Word Chain Between Two Words

Fanatics logoFanatics● MediumFULLTIMEPHONE SCREEN

Problem statement

You are given an array words of different lowercase words, and two of those words, start and end.

A word b can follow a word a when the first letter of b is the same as the last letter of a. A word chain is a list of words from words in which every word after the first can follow the word right before it.

Return the shortest word chain that begins with start and ends with end. The length of a chain is its number of words.

If several shortest chains exist, return the one that comes first when you compare the chains word by word: find the first position where they differ, and pick the chain whose word there comes first in dictionary order.

If no chain from start to end exists, return an empty array.

Function

shortestWordChain(words: String[], start: String, end: String) → String[]

Examples

Example 1

words = ["apple","egg","giraffe","elephant","tiger","rose"]start = "apple"end = "rose"return = ["apple","elephant","tiger","rose"]

The chain apple, egg, giraffe, elephant, tiger, rose works, but it has 6 words.

apple ends with e, so elephant can follow it right away. Then tiger follows elephant (t), and rose follows tiger (r). That chain has 4 words.

No shorter chain exists: a 3-word chain would need a word that starts with e and ends with r, and there is none.

Example 2

words = ["dog","gun","gin","neon"]start = "dog"end = "neon"return = ["dog","gin","neon"]

Both gun and gin start with g and end with n, so ["dog", "gun", "neon"] and ["dog", "gin", "neon"] are both shortest chains.

They first differ at the second word, and gin comes before gun in dictionary order, so the answer uses gin.

Example 3

words = ["cat","tub","bus","dog"]start = "cat"end = "dog"return = []

From cat you can go to tub and then to bus. No word starts with s, and no word ends with d, so dog can never be reached. The answer is an empty array.

Constraints

  • 2 <= words.length <= 2000
  • 1 <= words[i].length <= 10
  • words[i] contains only lowercase English letters.
  • All strings in words are different.
  • start and end are both in words, and start != end.
See Fanatics hiring insights
Saved
public String[] shortestWordChain(String[] words, String start, String end) {
    // Write your solution here.
}
Checking account…