Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# Shortest String Transformation Using A Dictionary Problem Statement

You are given a dictionary called `words` and two string arguments called `start` and `stop`. All given strings have equal length.

Transform string `start` to string `stop` one character per step using words from the dictionary. For example, "abc" → "abd" is a valid transformation step because only one character is changed ("c" → "d"), but "abc" → "axy" is not a valid one because two characters are changed ("b" → "x" and "c" → "y").

You need to find the shortest possible sequence of strings (two or more) such that:

1. First string is `start`.
2. Last string is `stop`.
3. Every string (except the first one) differs from the previous one by exactly one character.
4. Every string (except, possibly, first and last ones) are in the dictionary of `words`.

## Example One

``````{
"start": "bat",
}
``````

Output:

``````["bat", "bad", "had"]
``````

OR

``````["bat", "hat", "had"]
``````

In "bat", change "t" → "d" to get "bad".\ In "bad", change "b" → "h"to get "had".

OR

In "bat", change "b" → "h" to get "hat".\ In "hat", change "t" → "d" to get "had".

## Example Two

``````{
"words": [],
"start": bbb,
"stop": bbc
}
``````

Output:

``````["bbb", "bbc"]
``````

In "bbb", the last character to "b" and get "bbc".

## Example Three

``````{
"words": [],
"start": "zzzzzz",
"stop": "zzzzzz"
}
``````

Output:

``````["-1"]
``````

No sequence of strings exists that would satisfy all requirements. For example, ["zzzzzz", "zzzzzz"] does not satisfy requirement #3. In such situations, ["-1"] is the correct answer.

## Notes

• If two or more such sequences exist, return any.
• If no such sequence is there to be found, ["-1"] (a sequence of one string, "-1") is the correct answer.

Constraints:

• All input strings consist of lowercase English letters.
• 0 <= total number of characters in all dictionary `words` combined <= 105
• Strings in `words` are not in any particular order.
• There may be duplicates in `words`.

This problem can be solved using BFS.

# Shortest String Transformation Using A Dictionary Solution: Optimal

From current string, when we want to update neighbour strings (strings having different character at exactly one position), there are two methods possible:

1. Visit every string in `words` array and check. There are `no_of_words` strings in `words` array and each has length `length`. So, for one string to find neighbour strings, time taken will be O(noofwords * length). And we will find neighbours for O(noofwords) strings, hence time complexity of this solution will be O(noofwords2 * length). When `no_of_words` is big, this solution will time out.

2. For current string we will generate all possible strings having different character at exactly one position, and we will update strings that are in `words` array i.e. they are neighbours. We can use hashmap to check if any string is in `words` array or not in O(length) time, instead of O(noofwords * length) time using simple array search.

Now there can be O(26 * length) different strings having different character at exactly one position. And for each string we will spend O(length) time to check if it is in `words` array or not. We will find neighbours for O(noofwords) strings, hence time complexity of this solution will be O(noofwords * length2 * 26). Now when string length is high, this solution will time out.

So, we can combine both methods in one solution to bring down time complexity to O((noofwords * length * min((noofwords, 26 * length)). When `no_of_words <= 26 * length` use first method and when `no_of_words > 26 * length` use the second method!

Have a look at the solution provided by us, it contains necessary comments to understand the solution.

## Time Complexity

O(noofwords * length * min(noofwords, 26 * length)).

## Auxiliary Space Used

O(noofwords * length).

## Space Complexity

O(noofwords * length).

Space used by input: O(noofwords * length). Auxiliary space used: O(noofwords * length). Space used by output: O(noofwords * length). So, total space complexity: O(noofwords * length).

## Code For Shortest String Transformation Using A Dictionary Solution: Optimal

``````    /*
Asymptotic complexity in terms of the number of words \`no_of_words\` and the length of any word \`length\`:
* Time: O(no_of_words * length * minimum(no_of_words, 26 * length)).
* Auxiliary space: O(no_of_words * length).
* Total space: O(no_of_words * length).
*/

static int length, no_of_words;
static Queue<Integer> bfs_q;
static ArrayList<Boolean> visited;
static HashMap<String, Integer> position;
static HashMap<Integer, Integer> parent;

// Check if str1 and str2 differ by exactly one character.
static boolean only_one_char_difference(int length, String str1, String str2)
{
int difference = 0;
for (int i = 0; i < length; i++)
{
if (str1.charAt(i) != str2.charAt(i))
{
if (difference == 1)
{
return false;
}
difference++;
}
}
return difference == 1;
}

// Update neighbors using O(length * length * 26) method.
static void add_neighbours_with_method2(String current_word, int idx)
{
StringBuilder temp_str = new StringBuilder(current_word);
for (int i = 0; i < length; i++)
{
for (char ch = 'a'; ch <= 'z'; ch++)
{
if (ch == current_word.charAt(i))
{
continue;
}
// Store the original character, this will help to reverse the change.
char original_character = temp_str.charAt(i);
temp_str.setCharAt(i, ch);
// Check if new string is in words array or not.
int it = position.getOrDefault(temp_str.toString(), -1);
if (it != -1)
{
int position_of_current_word_in_words_array = it;
if (!visited.get(position_of_current_word_in_words_array))
{
visited.set(position_of_current_word_in_words_array, true);

// This string is visited by idx-th string.
// Insert this parent - child pair to construct the answer later.
parent.put(position_of_current_word_in_words_array, idx);

// This condition is used to check if the \`stop\` word is reached.
// The \`stop\` word was pushed at the end of the \`words\` array.
if (position_of_current_word_in_words_array == no_of_words - 1)
{
return;
}
}
}
temp_str.setCharAt(i, original_character);
}
}
}

// Update neighbors using O(no_of_words * length) method.
static void add_neighbours_with_method1(ArrayList<String> words, String current_word, int idx)
{
for (int i = 0; i < no_of_words; i++)
{
// If neighbor is not visited and has only one character different from current string.
if (!visited.get(i) && only_one_char_difference(length, current_word, words.get(i)))
{
visited.set(i, true);

// This string is visited by idx-th string.
// Insert this parent - child pair to construct the answer later.
parent.put(i, idx);

// This condition is used to check if the \`stop\` word is reached.
// The \`stop\` word was pushed at the end of the \`words\` array.
if (i == no_of_words - 1)
{
return;
}
}
}
}

static void bfs(ArrayList<String> words, String start, String stop)
{
// When no_of_words > length * 26, we are going to use method2.
// So, we need to use hash map for faster search.
// For search if string is present in words array or not in O(length) time.
if (no_of_words > length * 26)
{
for (int i = 0; i < no_of_words; i++)
{
position.put(words.get(i), i);
}
}
// -1 means start string.

visited = new ArrayList<>(Collections.nCopies(no_of_words, false));

while (!bfs_q.isEmpty())
{
int idx = bfs_q.poll();
// Stores string that is at the front of queue.
String current_word;
if (idx == -1)
{
current_word = start;
}
else
{
current_word = words.get(idx);
}
// Update the neighbors.
if (no_of_words <= length * 26)
{
}
else
{
}
}
}

static ArrayList<String> string_transformation(ArrayList<String> words, String start, String stop)
{
no_of_words = 0;
visited = new ArrayList<>();
position = new HashMap<String, Integer>();
parent = new HashMap<Integer, Integer>();
length = start.length();

// stop word needs to be added at the end of the dictionary words.
if (words.contains(stop)) {
words.remove(stop);
}

no_of_words = words.size();

bfs(words, start, stop);

// From parent information gathered from BFS, construct the actual string transformation.

int stop_index = no_of_words - 1;
// If stop string is not reached in BFS.
if (!parent.containsKey(stop_index))
{
}

// Start from stop string. Go to its parent, then its parent's parent... till we reach start string.
while (stop_index != -1)
{
stop_index = parent.get(stop_index);
}

// Reverse the \`answer\` array since it contains strings in the reverse order.
}

``````

We hope that these solutions to word ladder problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# Shortest String Transformation Using A Dictionary Problem Statement

You are given a dictionary called `words` and two string arguments called `start` and `stop`. All given strings have equal length.

Transform string `start` to string `stop` one character per step using words from the dictionary. For example, "abc" → "abd" is a valid transformation step because only one character is changed ("c" → "d"), but "abc" → "axy" is not a valid one because two characters are changed ("b" → "x" and "c" → "y").

You need to find the shortest possible sequence of strings (two or more) such that:

1. First string is `start`.
2. Last string is `stop`.
3. Every string (except the first one) differs from the previous one by exactly one character.
4. Every string (except, possibly, first and last ones) are in the dictionary of `words`.

## Example One

``````{
"start": "bat",
}
``````

Output:

``````["bat", "bad", "had"]
``````

OR

``````["bat", "hat", "had"]
``````

In "bat", change "t" → "d" to get "bad".\ In "bad", change "b" → "h"to get "had".

OR

In "bat", change "b" → "h" to get "hat".\ In "hat", change "t" → "d" to get "had".

## Example Two

``````{
"words": [],
"start": bbb,
"stop": bbc
}
``````

Output:

``````["bbb", "bbc"]
``````

In "bbb", the last character to "b" and get "bbc".

## Example Three

``````{
"words": [],
"start": "zzzzzz",
"stop": "zzzzzz"
}
``````

Output:

``````["-1"]
``````

No sequence of strings exists that would satisfy all requirements. For example, ["zzzzzz", "zzzzzz"] does not satisfy requirement #3. In such situations, ["-1"] is the correct answer.

## Notes

• If two or more such sequences exist, return any.
• If no such sequence is there to be found, ["-1"] (a sequence of one string, "-1") is the correct answer.

Constraints:

• All input strings consist of lowercase English letters.
• 0 <= total number of characters in all dictionary `words` combined <= 105
• Strings in `words` are not in any particular order.
• There may be duplicates in `words`.

This problem can be solved using BFS.

# Shortest String Transformation Using A Dictionary Solution: Optimal

From current string, when we want to update neighbour strings (strings having different character at exactly one position), there are two methods possible:

1. Visit every string in `words` array and check. There are `no_of_words` strings in `words` array and each has length `length`. So, for one string to find neighbour strings, time taken will be O(noofwords * length). And we will find neighbours for O(noofwords) strings, hence time complexity of this solution will be O(noofwords2 * length). When `no_of_words` is big, this solution will time out.

2. For current string we will generate all possible strings having different character at exactly one position, and we will update strings that are in `words` array i.e. they are neighbours. We can use hashmap to check if any string is in `words` array or not in O(length) time, instead of O(noofwords * length) time using simple array search.

Now there can be O(26 * length) different strings having different character at exactly one position. And for each string we will spend O(length) time to check if it is in `words` array or not. We will find neighbours for O(noofwords) strings, hence time complexity of this solution will be O(noofwords * length2 * 26). Now when string length is high, this solution will time out.

So, we can combine both methods in one solution to bring down time complexity to O((noofwords * length * min((noofwords, 26 * length)). When `no_of_words <= 26 * length` use first method and when `no_of_words > 26 * length` use the second method!

Have a look at the solution provided by us, it contains necessary comments to understand the solution.

## Time Complexity

O(noofwords * length * min(noofwords, 26 * length)).

## Auxiliary Space Used

O(noofwords * length).

## Space Complexity

O(noofwords * length).

Space used by input: O(noofwords * length). Auxiliary space used: O(noofwords * length). Space used by output: O(noofwords * length). So, total space complexity: O(noofwords * length).

## Code For Shortest String Transformation Using A Dictionary Solution: Optimal

``````    /*
Asymptotic complexity in terms of the number of words \`no_of_words\` and the length of any word \`length\`:
* Time: O(no_of_words * length * minimum(no_of_words, 26 * length)).
* Auxiliary space: O(no_of_words * length).
* Total space: O(no_of_words * length).
*/

static int length, no_of_words;
static Queue<Integer> bfs_q;
static ArrayList<Boolean> visited;
static HashMap<String, Integer> position;
static HashMap<Integer, Integer> parent;

// Check if str1 and str2 differ by exactly one character.
static boolean only_one_char_difference(int length, String str1, String str2)
{
int difference = 0;
for (int i = 0; i < length; i++)
{
if (str1.charAt(i) != str2.charAt(i))
{
if (difference == 1)
{
return false;
}
difference++;
}
}
return difference == 1;
}

// Update neighbors using O(length * length * 26) method.
static void add_neighbours_with_method2(String current_word, int idx)
{
StringBuilder temp_str = new StringBuilder(current_word);
for (int i = 0; i < length; i++)
{
for (char ch = 'a'; ch <= 'z'; ch++)
{
if (ch == current_word.charAt(i))
{
continue;
}
// Store the original character, this will help to reverse the change.
char original_character = temp_str.charAt(i);
temp_str.setCharAt(i, ch);
// Check if new string is in words array or not.
int it = position.getOrDefault(temp_str.toString(), -1);
if (it != -1)
{
int position_of_current_word_in_words_array = it;
if (!visited.get(position_of_current_word_in_words_array))
{
visited.set(position_of_current_word_in_words_array, true);

// This string is visited by idx-th string.
// Insert this parent - child pair to construct the answer later.
parent.put(position_of_current_word_in_words_array, idx);

// This condition is used to check if the \`stop\` word is reached.
// The \`stop\` word was pushed at the end of the \`words\` array.
if (position_of_current_word_in_words_array == no_of_words - 1)
{
return;
}
}
}
temp_str.setCharAt(i, original_character);
}
}
}

// Update neighbors using O(no_of_words * length) method.
static void add_neighbours_with_method1(ArrayList<String> words, String current_word, int idx)
{
for (int i = 0; i < no_of_words; i++)
{
// If neighbor is not visited and has only one character different from current string.
if (!visited.get(i) && only_one_char_difference(length, current_word, words.get(i)))
{
visited.set(i, true);

// This string is visited by idx-th string.
// Insert this parent - child pair to construct the answer later.
parent.put(i, idx);

// This condition is used to check if the \`stop\` word is reached.
// The \`stop\` word was pushed at the end of the \`words\` array.
if (i == no_of_words - 1)
{
return;
}
}
}
}

static void bfs(ArrayList<String> words, String start, String stop)
{
// When no_of_words > length * 26, we are going to use method2.
// So, we need to use hash map for faster search.
// For search if string is present in words array or not in O(length) time.
if (no_of_words > length * 26)
{
for (int i = 0; i < no_of_words; i++)
{
position.put(words.get(i), i);
}
}
// -1 means start string.

visited = new ArrayList<>(Collections.nCopies(no_of_words, false));

while (!bfs_q.isEmpty())
{
int idx = bfs_q.poll();
// Stores string that is at the front of queue.
String current_word;
if (idx == -1)
{
current_word = start;
}
else
{
current_word = words.get(idx);
}
// Update the neighbors.
if (no_of_words <= length * 26)
{
}
else
{
}
}
}

static ArrayList<String> string_transformation(ArrayList<String> words, String start, String stop)
{
no_of_words = 0;
visited = new ArrayList<>();
position = new HashMap<String, Integer>();
parent = new HashMap<Integer, Integer>();
length = start.length();

// stop word needs to be added at the end of the dictionary words.
if (words.contains(stop)) {
words.remove(stop);
}

no_of_words = words.size();

bfs(words, start, stop);

// From parent information gathered from BFS, construct the actual string transformation.

int stop_index = no_of_words - 1;
// If stop string is not reached in BFS.
if (!parent.containsKey(stop_index))
{
}

// Start from stop string. Go to its parent, then its parent's parent... till we reach start string.
while (stop_index != -1)
{
stop_index = parent.get(stop_index);
}

// Reverse the \`answer\` array since it contains strings in the reverse order.
}

``````

We hope that these solutions to word ladder problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as: