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

{
"words": ["cat", "hat", "bad", "had"],
"start": "bat",
"stop": "had"
}

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 <= 10⁵
• 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(noofwords² * 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 * length² * 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;
                          }
                          bfs_q.add(position_of_current_word_in_words_array);
                     }
                }
                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;
                }
                bfs_q.add(i);
            }
        }
    }

    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.
        bfs_q.add(-1);

        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)
            {
                add_neighbours_with_method1(words, current_word, idx);
            }
            else
            {
                add_neighbours_with_method2(current_word, idx);
            }
        }
    }

    static ArrayList<String> string_transformation(ArrayList<String> words, String start, String stop)
    {
        no_of_words = 0;
        bfs_q = new LinkedList<>();
        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);
        }
        words.add(stop);

        no_of_words = words.size();

        bfs(words, start, stop);

        // From parent information gathered from BFS, construct the actual string transformation.
        ArrayList<String> answer = new ArrayList<>();

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

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

        answer.add(start);
        // Reverse the \`answer\` array since it contains strings in the reverse order.
        Collections.reverse(answer);
        return answer;
    }

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:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.