Leetcode: Word Ladder

Difficulty: Medium

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1.    Only one letter can be changed at a time

2.    Each intermediate word must exist in the word list

For example,

Given:

beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",

return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Runtime Analysis:

First, we need to understand the problem and the approach we should take. Please read the Algorithmic Approach first.

Runtime: O(26n) 
Space: O(n) 

Algorithmic Approach:

This question requires a good understanding of BFS. Given an initial word to start with, we need to transform character by character to reach our final word. However, we cannot transform each character directly from our initial to final state because that particular word may not exist in our dictionary. We might have to transform to intermediary states to in order reach our final string.

See Example:

Dictionary = {"cat", "aat", "aag", "aog", "dog"}
Transformation = ["cat" => "aat" => "aag" => "aog" => "dog"]

Since we do not know which words exist in our dictionary, we would have to go through every alphabetical character (a-z) for every index in our string and check if that is a valid state.

The reason we are using BFS instead of DFS is because we are asked the compute the shortest transformation sequence. Due to this fact, we want to visit the neighbors that are closest distance first. 

We can implement BFS by using a Queue. We push our initial node on first. For each iteration, we pop off all elements in the queue (to process all nodes that are x distance away from our start). For each element, we check if it is equal to our final state, if so, we just return the distance. Otherwise, we push each of the node's neighbors back onto the queue.

In order to prevent cycles in the graph traversal, we remove words that we have already visited from the dictionary.

Java Code: 

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        
        Queue<String> queue = new LinkedList<String>();
        queue.add(beginWord);
        int count = 1;
        
        while(!queue.isEmpty()){
            
            int size = queue.size();
            
            for(int j = 0; j < size; j++){
                String word = queue.remove();
                
                if(word.equals(endWord)){
                    return count;
                }
                
                for(int i = 0; i < word.length(); i++){
                    for(char c = 'a'; c <= 'z'; c++){
                        if(c != word.charAt(i)){
                            char[] s = word.toCharArray();
                            s[i] = c;
                            String trans = new String(s);
                            
                            if(wordList.contains(trans)){
                                queue.add(trans);
                                wordList.remove(trans);
                            }
                        }
                    }
                }
            }
            
            count++;
        }
        
        return 0;
    }
}

Leetcode: Implement Queue Using Stacks

Difficulty: Easy

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Notes:

• You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Runtime Analysis:

Peek(): O(n)
Pop(): O(n)
Push(x): O(1)

Algorithmic Approach:

This question requires a basic understanding of Queues and Stacks. Queues are First In First Out Structures (FIFO) while Stacks are Last In First Out Structures (LIFO). When you use a Queue, you typically want to keep the original order of the elements added, visiting elements that you added first before elements that you added later. When you use a Stack, you want to reverse the order of elements added, visiting elements that you added last before elements that you added first.

Since the Stack reverses the order of elements added, using 2 Stacks will restore the original order. This is in essence to approach to solve this problem. We will use 2 Stacks to solve this Question: an "IN" Stack and an "OUT" Stack. 

When you:

1. Push(x): You simply add the element to a "IN" Stack.

2. Peek(x): Return the top element in the "OUT" Stack. If "OUT" Stack is empty, remove all elements in the "IN" Stack and push them to the "OUT" Stack (thus restoring the original order of elements), them simply return the top element.

3. Pop(x): Pop the top element in the "OUT" Stack. If "OUT" Stack is empty, remove all elements in the "IN" Stack and push them to the "OUT" Stack (thus restoring the original order of elements), them simply pop off the top element.

Java Code:

class MyQueue {
    
    Stack<Integer> in = new Stack();
    Stack<Integer> out = new Stack();
    
    // Push element x to the back of queue.
    public void push(int x) {
        in.push(x);
    }

    // Removes the element from front of queue.
    public void pop() {
        if(out.isEmpty()){
            while(!in.isEmpty()){
                out.push(in.pop());
            }
        }
        out.pop();
    }

    // Gets element from front of queue.
    public int peek() {
        if(out.isEmpty()){
            while(!in.isEmpty()){
                out.push(in.pop());
            }
        }
        
        return out.peek();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}