Friday, July 17, 2015

Word Ladder | Leetcode

Given two words (beginWord and endWord), and a dictionary, 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 dictionary
For example,

Given:
start = "hit"
end = "cog"
dict = ["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.
---

Solution: Perform a Breadth-First Search (BFS) by using a queue to hold the nodes. For each word, for each character, iterate from 'a' to 'z' to form all possible next words from the current word. For each next possible word, if it were found in the dictionary, then append it to the queue, with a cost of one more than the current cost.

The key is to remove words from the dictionary as you encounter them. This will ensure that you will not get into an infinite loop.
public class Solution {
    private static class WordNode {
        private String word;
        private int cost;
        
        private WordNode(String word, int cost) {
            this.word = word;
            this.cost = cost;
        }
    }
    
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        if (beginWord.equals(endWord)) return 1;

        LinkedList<WordNode> queue = new LinkedList<>();
        queue.add(new WordNode(beginWord, 1));

        do {
            WordNode wordNode = queue.removeFirst();
            char[] a = wordNode.word.toCharArray();

            for (int i = 0; i < a.length; i++) {
                char savedChar = a[i];

                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (ch == savedChar) continue;
                    a[i] = ch;
                    String newWord = new String(a);
                    if (newWord.equals(endWord)) return wordNode.cost + 1;
                    if (wordDict.contains(newWord)) {
                        queue.addLast(new WordNode(newWord, wordNode.cost + 1));
                        wordDict.remove(newWord);
                    }
                }

                a[i] = savedChar;
            }
        } while (!queue.isEmpty());

        return 0;
    }
}

Thursday, July 16, 2015

Word Ladder II | Leetcode

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary
For example,

Given:

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]
Note:
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
---

Solution: https://leetcode.com/discuss/9523/share-two-similar-java-solution-that-accpted-by-oj

Algorithm 1: Slow (Will Not Pass Leetcode)
public class Solution {
    private static class WordNode {
        private final String word;
        private final int cost;
        private final WordNode prev;
        
        private WordNode(String word, int cost, WordNode prev) {
            this.word = word;
            this.cost = cost;
            this.prev = prev;
        }
    }
    
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> answer = new ArrayList<>();
        LinkedList<WordNode> queue = new LinkedList<>();
        queue.addLast(new WordNode(start, 1, null));
        dict.remove(start);
        int minCost = 0;
        
        do {
            WordNode node = queue.removeFirst();
            if (minCost != 0 && node.cost > minCost) break;
            
            char[] a = node.word.toCharArray();
            for (int i = 0; i < a.length; i++) {
                char ch = a[i];

                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == ch) continue;
                    a[i] = c;
                    String s = new String(a);
                    if (s.equals(end)) {
                        if (minCost == 0 || node.cost == minCost) {
                            answer.add(formResult(node, end));
                            minCost = node.cost;
                            continue;
                        }
                    }
                    if (!dict.contains(s)) continue;
                    queue.addLast(new WordNode(s, node.cost + 1, node));
                }
                
                a[i] = ch;
            }
        } while (!queue.isEmpty());
        
        return answer;
    }
    
    private static List<String> formResult(WordNode node, String end) {
        LinkedList<String> list = new LinkedList<>();
        list.addFirst(end);
        while (node != null) {
            list.addFirst(node.word);
            node = node.prev;
        }
        return list;
    }
}
Algorithm 2: Fast (Will Pass Leetcode)
public class Solution {
    private List<List<String>> answer = new ArrayList<List<String>>();
    private LinkedList<String> backTraceList = new LinkedList<String>();
    private Map<String, List<String>> adjacentWordsMap = new HashMap<String, List<String>>();

    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        int curr = 1;
        int next = 0;
        boolean found = false;

        LinkedList<String> queue = new LinkedList<>();
        Set<String> unvisited = new HashSet<String>(dict);
        Set<String> visited = new HashSet<String>();

        queue.add(start);
        unvisited.add(end);
        unvisited.remove(start);

        do {
            String word = queue.removeFirst();
            curr--;
            char[] a = word.toCharArray();
            for (int i = 0; i < word.length(); i++) {
                char savedChar = a[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (ch == savedChar) continue;
                    a[i] = ch;
                    String newWord = new String(a);
                    if (unvisited.contains(newWord)) {
                        // Key statement - avoid duplicate queue insertion.
                        if (!visited.contains(newWord)) {
                            visited.add(newWord);
                            next++;
                            queue.addLast(newWord);
                        }

                        // Build adjacency graph.
                        List<String> list = adjacentWordsMap.get(newWord);
                        if (list == null) {
                            list = new LinkedList<String>();
                            adjacentWordsMap.put(newWord, list);
                        }
                        list.add(word);

                        if (newWord.equals(end)) found = true;
                    }
                }
                a[i] = savedChar;
            }
            
            if (curr == 0) {
                if (found) break;
                curr = next;
                next = 0;
                unvisited.removeAll(visited);
                visited.clear();
            }
        } while (!queue.isEmpty());

        backTrace(end, start);

        return answer;
    }

    private void backTrace(String word, String start) {
        if (word.equals(start)) {
            backTraceList.addFirst(start);
            answer.add(new ArrayList<String>(backTraceList));
            backTraceList.removeFirst();
            return;
        }
        backTraceList.addFirst(word);
        if (adjacentWordsMap.containsKey(word)) {
            for (String s : adjacentWordsMap.get(word)) {
                backTrace(s, start);
            }
        }
        backTraceList.removeFirst();
    }
}

Friday, July 10, 2015

Valid Palindrome | Leetcode

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
 
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.

---

Solution: Maintain two pointers, one pointing to the beginning of the string, and the other pointing to the end of the string. Advance first pointer to a position where it is an alpha-numeric character. Retreat last pointer to a position where it is an alpha-numeric character. If the character at the first pointer is not the same as the character at the last pointer, then return false. Repeat until done (first >= last). Return true if you did not discover any inequalities.
public class Solution {
    public boolean isPalindrome(String s) {
        int first = 0;
        int last = s.length() - 1;
        int ch1, ch2;
        
        while (first < last) {
            while (true) {
                ch1 = s.charAt(first++);
                if (Character.isLetterOrDigit(ch1)) break;
                if (first >= last) return true;
            }
            
            while (true) {
                ch2 = s.charAt(last--);
                if (Character.isLetterOrDigit(ch2)) break;
                if (first >= last) return true;
            }
            
            if (Character.toUpperCase(ch1) != Character.toUpperCase(ch2)) {
                return false;
            }
        }
        
        return true;
    }
}

Binary Tree Maximum Path Sum | Leetcode

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,
       1
      / \
     2   3
Return 6.

---

Solution: Recurse through the tree, keeping track of the maximum path sum ever found. For each node, we can compute the max by considering branching out to both left and right sub-trees. But to return the max sum for the current node, we can only take one path, either the node itself only, or the node + the left sub-tree, or the node + the right sub-tree. Return the maximum path sum ever found as the answer.
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int maxSum;
    
    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        maxSum = root.val;
        recurse(root);
        return maxSum;
    }
    
    private int recurse(TreeNode node) {
        if (node == null) return 0;
        
        int left = recurse(node.left);
        int right = recurse(node.right);
        
        // For the current node, pick only a single path.
        int current = Math.max(node.val, Math.max(node.val + left, node.val + right));
        
        // For maxSum, we can pick two paths both branching out from node.
        maxSum = Math.max(maxSum, Math.max(current, node.val + left + right));
        
        return current;
    }
}

Thursday, July 9, 2015

Best Time to Buy and Sell Stock III | Leetcode

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

---

Solution: Use linear dynamic programming twice on the array. The first time is from left to right. The second time is from right to left. Each time, capture the maximum profit possible until the given point, either from the left end or the right end. At the end, go through the array one last time, and split the array into two parts, getting the maximum profit from the left part plus the right part.
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;

        int[] leftProfit = new int[prices.length];
        int[] rightProfit = new int[prices.length];
        
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            int left = (min < prices[i]) ? (prices[i] - min) : 0;
            leftProfit[i] = Math.max(left, leftProfit[i - 1]);
            min = Math.min(min, prices[i]);
        }
        
        int max = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            int right = (max > prices[i]) ? (max - prices[i]) : 0;
            rightProfit[i] = Math.max(right, rightProfit[i + 1]);
            max = Math.max(max, prices[i]);
        }
        
        int maxProfit = 0;
        for (int i = -1; i < prices.length; i++) {
            int left = (i < 0) ? 0 : leftProfit[i];
            int right = (i + 1 < prices.length) ? rightProfit[i + 1] : 0;
            maxProfit = Math.max(maxProfit, left + right);
        }
        
        return maxProfit;
    }
}

Tuesday, July 7, 2015

Best Time to Buy and Sell Stock II | Leetcode

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

---

Solution: Iterate through the prices array from beginning to end. Find the current lowest price, which is defined as the price which is lower than its next price. Then find the current highest price, which is defined as the price which is higher than its next price. Capture the profit by subtracting the current lowest price from the current highest price. Repeat until we reach the end of the loop.

The boundary cases are very tricky, so have to be extra careful.
public class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        int last = prices.length - 1;
        int i = 0;
        do {
            // Find the current lowest point.
            while (i < last && prices[i] >= prices[i + 1]) i++;
            if (i >= last) break;
            int lo = prices[i++];
            
            // Find the current highest point.
            while (i <= last && prices[i - 1] <= prices[i]) i++;
            int hi = prices[i - 1];
            
            // Capture current profit if any.
            if (hi > lo) profit += hi - lo;
        } while (i < last);
        return profit;
    }
}

Best Time to Buy and Sell Stock | Leetcode

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

---

Solution: Go through each price, at the same time keeping the minimum price and maximum profit ever seen so far. By using the current price and this minimum price, we can calculate the maximum profit attainable.
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            minPrice = Math.min(minPrice, prices[i]);
        }
        return maxProfit;
    }
}