DAY 35- Word Ladder I

Hey everyone! Welcome back to another day of problem-solving. It's day 35, and I'm still going strong on my quest for consistency. Today, we have an interesting problem to tackle. But before we dive in, let's make sure we're all on the same page.

Incase you are unfamiliar with graphs I suggest reading the previous article 32 && 33. It also contains the links to valuable resources.

Question :

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:

• Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
• Output: 5
• Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

• Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
• Output: 0
• Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Intuition:

Let's start by understanding the question first and then proceed towards a solution.

• We will be given a word to begin with (say "hit" from Example 1) and we will be given a word to end with(sk in our wordList).

• What we can essentially do is starting from our beginWord, we can make one change to any one character in that word.

• We can make any change but we can only proceed towards a word that exists in our wordList. Suppose if we change our word "hit" to "aik" replacing h with a. Since it's not in the wordList, it's not a valid substitution.

• Replacing i in "hit" with character 'o' makes it "hot". This exists in our wordList so this is a valid replacement.

• We can either proceed with this replacement of we can try other replacements.

• If we choose to go with this replacement must go through the same process of replacing one character.

• We must repeat this process till we reach our finalWord or endWord.

• Although it does not appear to be a graph problem at first, it does include the bfs approach for solving it.

Let's start with the the approach:

Approach:

• What we are essentially going to do is brute force.
• Firstly, we start by creating a queue data structure in order to store the word and the length of the sequence to reach that word as a pair. We store them in form of {word, steps}.
• Then, we push the beginWord into the queue with length as ‘1’ indicating that this is the word from which the sequence needs to start from.
• We now create a hash set wherein, we put all the elements in wordList to keep a check on if we’ve visited that word before or not. In order to mark a word as visited here, we simply delete the word from the hash set. There is no point in visiting someone multiple times during the algorithm.
• Now, we pop the first element out of the queue and carry out the BFS traversal where, for each word popped out of the queue, we try to replace every character with ‘a’ – ‘z’, and we get a transformed word. We check if the transformed word is present in the wordList or not.
• If the word is present, we push it in the queue and increase the count of the sequence by 1 and if not, we simply move on to replacing the original character with the next character.
• We do this until we have reached our final word or else we can say that our queue is empty.

Code:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        queue<pair<string,int>> q;
        q.push({beginWord,1});
        unordered_set<string> st(wordList.begin(),wordList.end());
        st.erase(beginWord);

        while(!q.empty()){
            string word = q.front().first;
            int steps = q.front().second;
            q.pop();
            if(word == endWord){
                return steps;
            }
            for(int i = 0; i < word.size(); i++){
                char original = word[i];
                for(char ch = 'a'; ch <= 'z'; ch++){
                    word[i] = ch;
                    if(st.find(word) != st.end()){
                    st.erase(word);
                    q.push({word,steps+1});

                    }

                }
                word[i] = original;
            }
        }
    return 0;
    }
};

Complexity Analysis:

• Time COmplexity: O(WordLength * N * logN)
• Space COmplexity: O(N) + O(N).

Thanks for reading. Feedback is highly appreciated.