Leetcode: Unique Word Abbreviation

An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:

a) it                      --> it    (no abbreviation)

     1
b) d|o|g                   --> d1g

              1    1  1
     1---5----0----5--8
c) i|nternationalizatio|n  --> i18n

              1
     1---5----0
d) l|ocalizatio|n          --> l10n

Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word's abbreviation is unique if no other word from the dictionary has the same abbreviation.

Example: 

Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

Understand the problem:
The question is a little bit tricky. 
There are only 2 conditions we return true for isUnique("word")
1. The abbr does not appear in the dict. 
2. The abbr is in the dict && the word appears one and only once in the dict. 

Code (Java): (WRONG SOLUTION)

public class ValidWordAbbr {
    private Map<String, String> map;
    public ValidWordAbbr(String[] dictionary) {
        this.map = new HashMap<>();
        
        for (String word : dictionary) {
            String abbr = toAbbr(word);
            if (map.containsKey(abbr)) {
                map.put(abbr, "");
            } else {
                map.put(abbr, word);
            }
        }
    }

    public boolean isUnique(String word) {
        String abbr = toAbbr(word);
        if (!map.containsKey(abbr) || map.get(abbr).equals(word)) {
            return true;
        } else {
            return false;
        }
    }
    
    private String toAbbr(String s) {
        if (s == null || s.length() <= 2) {
            return s;
        }
        
        int len = s.length() - 2;
        
        String result = s.charAt(0) + "" + len + s.charAt(s.length() - 1);
        
        return result;
    }
}
// Your ValidWordAbbr object will be instantiated and called as such:
// ValidWordAbbr vwa = new ValidWordAbbr(dictionary);
// vwa.isUnique("Word");
// vwa.isUnique("anotherWord");

Update on 9/26/15:
The solution above presumes that the dict does not contains duplicates. However, the OJ updates its test case that 

Input:["a","a"],isUnique("a")

Output:[false]

Expected:[true]

So the new solution we need to use two dictionaries, one save the abbr format and the other saves the original dict. The value stores the frequencies of each word. 

So how to determine if a word is unique in the abbrivation? There are still two cases to consider: 
1. If the abbr of the input word does not appear in the abbr dict, return true;
2. If the abbr of the input word DOES appears in the abbr dict, we must make sure the input word is in the dictionary AND the its abbreviation format can only appear once in the abbr dict. 
  -- Now here comes to the corner case that the dict contains duplicates. In this case, both the dict and abbr dict will store "a", 2. So in this way, a does not appear only once! So the solution to handle this edge case is we must make sure the word freq in the dict and abbr dict is exactly the same. So we can make sure the word has no other duplicated abbrivations in the abbr dict. 

Code (Java):

public class ValidWordAbbr {
    private Map<String, Integer> abbrDict;
    private Map<String, Integer> dict;
    public ValidWordAbbr(String[] dictionary) {
        abbrDict = new HashMap<>();
        dict = new HashMap<>();
        
        
        for (String word : dictionary) {
            
            if (dict.containsKey(word)) {
                int freq = dict.get(word);
                dict.put(word, freq + 1);
            } else {
                dict.put(word, 1);
            }
            
            String abbr = abbreviation(word);
            if (abbrDict.containsKey(abbr)) {
                int freq = abbrDict.get(abbr);
                abbrDict.put(abbr, freq + 1);
            } else {
                abbrDict.put(abbr, 1);
            }
        }
    }

    public boolean isUnique(String word) {
        if (word == null || word.length() == 0) {
            return true;
        }
        
        String abbr = abbreviation(word);
        if (!abbrDict.containsKey(abbr)) {
            return true;
        } else {
            if (dict.containsKey(word) && dict.get(word) == abbrDict.get(abbr)) {
                return true;
            }
        }
        
        return false;
    }
    
    private String abbreviation(String word) {
        if (word.length() <= 2) {
            return word;
        }
        
        StringBuffer sb = new StringBuffer();
        sb.append(word.charAt(0));
        sb.append(word.length() - 2);
        sb.append(word.charAt(word.length() - 1));
        
        return sb.toString();
    }
}

Update on 11/9/15:

public class ValidWordAbbr {
    private Set<String> uniqueDict;
    private Map<String, String> abbrDict;

    public ValidWordAbbr(String[] dictionary) {
        uniqueDict = new HashSet<>();
        abbrDict = new HashMap<>();
        
        for (String word : dictionary) {
            if (!uniqueDict.contains(word)) {
                String abbr = getAbbr(word);
                if (!abbrDict.containsKey(abbr)) {
                    abbrDict.put(abbr, word);
                } else {
                    abbrDict.put(abbr, "");
                }
                
                uniqueDict.add(word);
            }
        }
    }

    public boolean isUnique(String word) {
        if (word == null || word.length() == 0) {
            return true;
        }
        
        String abbr = getAbbr(word);
        if (!abbrDict.containsKey(abbr) || abbrDict.get(abbr).equals(word)) {
            return true;
        } else {
            return false;
        }
    }
    
    private String getAbbr(String word) {
        if (word == null || word.length() < 3) {
            return word;
        }
        
        StringBuffer sb = new StringBuffer();
        sb.append(word.charAt(0));
        sb.append(word.length() - 2);
        sb.append(word.charAt(word.length() - 1));
        
        return sb.toString();

    }
    
}


// Your ValidWordAbbr object will be instantiated and called as such:
// ValidWordAbbr vwa = new ValidWordAbbr(dictionary);
// vwa.isUnique("Word");
// vwa.isUnique("anotherWord");

Leetcode: Word Pattern

Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

1. pattern = "abba", str = "dog cat cat dog" should return true.
2. pattern = "abba", str = "dog cat cat fish" should return false.
3. pattern = "aaaa", str = "dog cat cat dog" should return false.
4. pattern = "abba", str = "dog dog dog dog" should return false.

Notes:

1. patterncontains only lowercase alphabetical letters, and str contains words separated by a single space. Each word in str contains only lowercase alphabetical letters.
2. Both pattern and str do not have leading or trailing spaces.
3. Each letter in pattern must map to a word with length that is at least 1.

Understand the problem:
The problem can be solved by using hash map. Note that some edge cases must be considered:
1. It must be a one-one mapping. e.g. 
"abba", "dog dog dog dog" => false, since a and b maps to the dog.
"aaaa", "dog cat cat dog" => false, since a maps to both dog and cat. 

So we may use two hash tables to maintain such a one-one mapping relationship. Note that in Java we may use map.containsValue(). 

2. The length of the pattern and number of tokens in the str must be the same. Otherwise, return false; 

Code (Java):

public class Solution {
    public boolean wordPattern(String pattern, String str) {
        if (pattern == null || pattern.length() == 0 || str == null || str.length() == 0) {
            return false;
        }

        String[] tokens = str.split(" ");
        
        if (pattern.length() != tokens.length) {
            return false;
        }

        Map<String, Character> inverseMap = new HashMap<>();
        Map<Character, String> map = new HashMap();
        
        int i = 0;
        for (i = 0; i < pattern.length(); i++) {
            char digit = pattern.charAt(i);
            
            String token = tokens[i];
            
            // Check the one-one mapping
            if (!map.containsKey(digit) && !inverseMap.containsKey(token)) {
                map.put(digit, token);
                inverseMap.put(token, digit);
            } else if (map.containsKey(digit) && inverseMap.containsKey(token)) {
                String token1 = map.get(digit);
                char digit1 = inverseMap.get(token);
                
                if (!token1.equals(token) || digit != digit1) {
                    return false;
                }
            } else {
                return false;
            }
        }
        
        return true;
    }
}

Leetcode: Encode and Decode Strings

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

Note:

• The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
• Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
• Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.

Understand the problem:
This is just an implementation problem. The key is how to separate the list of strings during the serialization process so we can decode the string in the de-serialization process.

One way we can think of is to use the number at front. e.g. abcdef, we can store 6abcdef. 
However, what if the string also starts from numbers, e.g. 123abc. In this case, what we stored is 6123abc, which is wrong. Therefore, we need to use another divider to divide the length of the string with the string itself. In this solution, we just use '#'. 

One thing needs to be careful in this such kind problem is the length of the string, which is in the form of string, is not a single character. Therefore, we need to parse the string until we see the divider. 

Code (Java):

public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        if (strs == null || strs.size() == 0) {
            return "";
        }
        
        StringBuffer sb = new StringBuffer();
        
        for (String str : strs) {
            int len = str == null ? 0 : str.length();
            sb.append(len);
            sb.append('#');
            sb.append(str);
        }
        
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }
        
        int i = 0;
        while (i < s.length()) {
            int len = 0;
            // Get length
            while (i < s.length() && s.charAt(i) != '#') {
                len = len * 10 + Character.getNumericValue(s.charAt(i));
                i++;
            }
            
            String str = s.substring(i + 1, i + len + 1);
            result.add(str);
            i = i + len + 1;
        }
        
        return result;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));

Update on 1/27/15:

public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        if (strs == null || strs.size() == 0) {
            return "";
        }
        StringBuffer sb = new StringBuffer();
        
        for (String str : strs) {
            if (str == null || str.length() == 0) {
                sb.append("0#");
            } else {
                sb.append(str.length() + "#" + str);
            }
        }
        
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> strs = new ArrayList<>();
        
        if (s == null || s.length() == 0) {
            return strs;
        }
        
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (j < s.length() && Character.isDigit(s.charAt(j))) {
                j++;
            }
            
            int num = Integer.parseInt(s.substring(i, j));
            i = j;
            i++; // skip '#'
            if (num == 0) {
                strs.add("");
            } else {
                strs.add(s.substring(i, i + num));
            }
            
            i += num;
        }
        
        return strs;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs)); 

Leetcode: Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Understand the problem:
The question can be solved by using divide-and-conquer. We first cut the expression into two halves and calculate the list of result for each half. Then we traverse the two lists and get the final result. 

Code (Java):

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result = new ArrayList<>();
        if (input == null || input.length() == 0) {
            return result;
        }
        
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            
            if (!isOperator(c)) {
                continue;
            }
            
            List<Integer> left = diffWaysToCompute(input.substring(0, i));
            List<Integer> right = diffWaysToCompute(input.substring(i + 1));
            
            for (int num1 : left) {
                for (int num2 : right) {
                    int val = calculate(num1, num2, c);
                    result.add(val);
                }
            }
        }
        
        // only contains one number
        if (result.isEmpty()) {
            result.add(Integer.parseInt(input));
        }
        
        return result;
    }
    
    private int calculate(int num1, int num2, char operator) {
        int result = 0;
        
        switch(operator) {
            case '+' : result = num1 + num2;
            break;
            
            case '-' : result = num1 - num2;
            break;
            
            case '*' : result = num1 * num2;
            break;
        }
        
        return result;
    }
    
    private boolean isOperator(char operator) {
        return (operator == '+') || (operator == '-') || (operator == '*');
    }
}

Summary:
The problem itself is not hard. The essence of the problem is to compute the different ways to compute the expression. There is only one trick here is how to handle the input has only one number there, e.g. "1". Then we need to add the number into the result list. The idea is to check if the result is empty after the divide-and-conquer step. If it is empty, means only one number left in the input. Note that we cannot check using if the first character of the input string is digit, because each and every input string starts from a number. 

Leetcode: Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Understand the problem:
The straight-forward solution is: find the longest palindrome substring starting with s[0]. Then insert the remaining of the string s to the front in a reverse order.

Code (Java):

public class Solution {
    public String shortestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int maxLen = 0;
        // Step 1: find the longest palindromic substring including s.charAt(0)
        for (int i = 0; i < s.length(); i++) {
            // Odd
            int p = i - 1;
            int q = i + 1;
            int len = 1;
            while (p >= 0 && q < s.length() && s.charAt(p) == s.charAt(q)) {
                len += 2;
                p--;
                q++;
            }
            
            if (p == -1 && len > maxLen) {
                maxLen = len;
            }
            
            // Even
            p = i;
            q = i + 1;
            len = 0;
            while (p >= 0 && q < s.length() && s.charAt(p) == s.charAt(q)) {
                p--;
                q++;
                len += 2;
            }
            
            if (p == -1 && len > maxLen) {
                maxLen = len;
            }
        }
        
        int j = maxLen;
        StringBuffer sb = new StringBuffer();
        for (int m = s.length() - 1; m >= j; m--) {
            sb.append(s.charAt(m));
        }
        
        sb.append(s);
        
        return sb.toString();
    }
}

Analysis:
The time complexity to find out the longest palindrome substring starting from s[0] is O(n^2). So the overall time complexity is O(n^2) as well. 

KMP solution:

Leetcode: Word search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

Note:
You may assume that all inputs are consist of lowercase letters a-z.

click to show hint.

You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?

If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: Implement Trie (Prefix Tree) first.

A time limit exceed solution:
Use a trie to save the word which does not in the board. So each time for a new word, we first search if the prefix exist in the trie. If yes, no need to search the board again. 
Simply put, the trie stores the prefix which does not exist in the board, so we don't need to waste of time to search again and again. 

Code (Java):

public class Solution {
    private int rows;
    private int cols;
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<String>();
        if (board == null || board.length == 0 || words == null || words.length == 0) {
            return result;
        } 
        
        Set<String> set = new HashSet<String>();
        
        Trie trie = new Trie();
        
        this.rows = board.length;
        this.cols = board[0].length;
        
        for (String word : words) {
            if (trie.searchPrefix(word) == false) {
                if (searchBoard(board, word)) {
                    if (!set.contains(word)) {
                        set.add(word);
                    }
                } else {
                    trie.insert(word);
                }
            } else {
                trie.insert(word);
            }
        }
        
        return new ArrayList<String>(set);
    }
    
    private boolean searchBoard(char[][] board, String word) {
        boolean[][] visited = new boolean[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (searchBoardHelper(board, i, j, word, 0, visited)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean searchBoardHelper(char[][] board, int row, int col, String word, int index, boolean[][] visited) {
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return false;
        }
        
        if (visited[row][col]) {
            return false;
        }
        
        if (board[row][col] != word.charAt(index)) {
            return false;
        }
        
        visited[row][col] = true;
        
        if (index == word.length() - 1 && board[row][col] == word.charAt(index)) {
            return true;
        }
        
        boolean ret; 
        ret = searchBoardHelper(board, row - 1, col, word, index + 1, visited) ||
              searchBoardHelper(board, row + 1, col, word, index + 1, visited) ||
              searchBoardHelper(board, row, col - 1, word, index + 1, visited) ||
              searchBoardHelper(board, row, col + 1, word, index + 1, visited);
        
        visited[row][col] = false;
        
        return ret;
    }
    
    class Trie {
        private TrieNode root = new TrieNode();
        
        // Insert a word
        void insert(String s) {
            TrieNode curr = root;
            int offset = 'a';
            for (int i = 0; i < s.length(); i++) {
                char character = s.charAt(i);
                if (curr.children[character - offset] == null) {
                    curr.children[character - offset] = 
                        new TrieNode(character, i == s.length() - 1 ? true : false);
                } else {
                    if (i == s.length() - 1) {
                        curr.children[character - offset].leaf = true;
                    }
                }
                curr = curr.children[character - offset];
            }
        }
        
        // Search for prefix
        boolean searchPrefix(String s) {
            TrieNode curr = root;
            int offset = 'a';
            for (int i = 0; i < s.length(); i++) {
                char character = s.charAt(i);
                if (curr.children[character - offset] == null) {
                    return false;
                } else if (curr.children[character - offset] != null && curr.children[character - offset].leaf) {
                    return true;
                }
                
                curr = curr.children[character - offset];
            }
            
            return false;
        }
    }
    
    class TrieNode {
        char val;
        boolean leaf;
        TrieNode[] children;
        
        public TrieNode() {
            this.val = '\0';
            this.children = new TrieNode[26];
        } 
        
        public TrieNode(char val, boolean leaf) {
            this.val = val;
            this.leaf = leaf;
            this.children = new TrieNode[26];
        }
    }
}

Code (Java):

public class Solution {
    private int rows;
    private int cols;
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<String>();
        if (board == null || board.length == 0 || words == null || words.length == 0) {
            return result;
        } 
        
        Set<String> set = new HashSet<String>();
        
        Trie trie = new Trie();
        
        this.rows = board.length;
        this.cols = board[0].length;
        
        // Step 1: insert all words into a trie
        for (String word : words) {
            trie.insert(word);
        }
        
        // Step 2: search the board
        boolean[][] visited = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                searchBoardHelper(board, i, j, "", visited, trie, set);
            }
        }
        
        return new ArrayList<String>(set);
    }
    
    
    private void searchBoardHelper(char[][] board, int row, int col, String word, 
                                      boolean[][] visited, Trie trie, Set<String> set) {
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return;
        }
        
        if (visited[row][col]) {
            return;
        }
        
        word += board[row][col];
        
        if (!trie.searchPrefix(word)) {
            return;
        }
        
        if (trie.search(word)) {
            set.add(word);
        }
        
        visited[row][col] = true;
        
        searchBoardHelper(board, row - 1, col, word, visited, trie, set);
        searchBoardHelper(board, row + 1, col, word, visited, trie, set);
        searchBoardHelper(board, row, col - 1, word, visited, trie, set);
        searchBoardHelper(board, row, col + 1, word, visited, trie, set);
        
        visited[row][col] = false;
    }
    
    class Trie {
        private TrieNode root = new TrieNode();
        
        // Insert a word
        void insert(String s) {
            TrieNode curr = root;
            int offset = 'a';
            for (int i = 0; i < s.length(); i++) {
                char character = s.charAt(i);
                if (curr.children[character - offset] == null) {
                    curr.children[character - offset] = 
                        new TrieNode(character, i == s.length() - 1 ? true : false);
                } else {
                    if (i == s.length() - 1) {
                        curr.children[character - offset].leaf = true;
                    }
                }
                curr = curr.children[character - offset];
            }
        }
        
        
        // Search a word
        boolean search(String s) {
            TrieNode curr = root;
            int offset = 'a';
            for (int i = 0; i < s.length(); i++) {
                char character = s.charAt(i);
                if (curr.children[character - offset] == null) {
                    return false;
                }
                curr = curr.children[character - offset];
            }
            
            if (curr != null && !curr.leaf) {
                return false;
            }
            
            return true;
        }
        
        // Search for prefix
        boolean searchPrefix(String s) {
            TrieNode curr = root;
            int offset = 'a';
            for (int i = 0; i < s.length(); i++) {
                char character = s.charAt(i);
                if (curr.children[character - offset] == null) {
                    return false;
                } 
                
                curr = curr.children[character - offset];
            }
            
            return true;
        }
    }
    
    class TrieNode {
        char val;
        boolean leaf;
        TrieNode[] children;
        
        public TrieNode() {
            this.val = '\0';
            this.children = new TrieNode[26];
        } 
        
        public TrieNode(char val, boolean leaf) {
            this.val = val;
            this.leaf = leaf;
            this.children = new TrieNode[26];
        }
    }
}

Analysis:
Let's think about the naive solution first. The naive solution is we search the board for each board. So for the dict with n words, and assume the ave. length of each word has length of m. Then without using a Trie, the time complexity would be O(n * rows * cols  * 4^m). 

Now let's analyze the time complexity of using a Trie. We put each word into the trie. Search in the Trie takes O(m) time, so the time complexity would be O(rows * cols * m * 4^m). Since mostly m << n, using a trie would save lots of time. 

A better solution:
The key observation with the previous solution is we don't need to search the trie for each prefix from the root; Instead, we can keep track of the current pointer to the trie. The time complexity is  O(rows * cols * 4^m).

Code (Java):

public class Solution {
    /**
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    public List<String> wordSearchII(char[][] board, List<String> words) {
        List<String> ans = new ArrayList<>();
        if (board == null || board[0] == null || words == null) {
            return ans;
        }

        Set<String> set = new HashSet<>();
        boolean[][] visited = new boolean[board.length][board[0].length];

        // step 1: create a trie and put words into the trie
        //
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }

        // step 2: scan the board and check if the word in the trie
        //
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                wordSearchHelper(i, j, board, visited, set, trie.root);
            }
        }

        return new ArrayList<>(set);
    }

    private void wordSearchHelper(int row, int col, char[][] board, boolean[][] visited, Set<String> set, TrieNode p) {
        int m = board.length;
        int n = board[0].length;

        if (row < 0 || row >= m || col < 0 || col >= n || visited[row][col]) {
            return;
        }

        char c = board[row][col];

        if (p.children[c - 'a'] == null) {
            return;
        }

        visited[row][col] = true;
        p = p.children[c - 'a'];

        if (!p.word.isEmpty()) {
            set.add(p.word);
        }

        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int i = 0; i < 4; i++) {
            wordSearchHelper(row + dirs[i][0], col + dirs[i][1], board, visited, set, p);
        }

        visited[row][col] = false;
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            if (p.children[c - 'a'] == null) {
                p.children[c - 'a'] = new TrieNode();
            }

            p = p.children[c - 'a'];
        }

        p.word = word;
    }
}

class TrieNode {
    TrieNode[] children;
    String word;

    public TrieNode() {
        children = new TrieNode[26];
        word = "";
    }
}

Update on 1/23/2021:

public class Solution {
    /**
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    public List<String> wordSearchII(char[][] board, List<String> words) {
        // write your code here
        List<String> res = new ArrayList<>();
        if (board == null || board.length == 0 || words == null || words.size() == 0) {
            return res;
        }
        
        Trie trie = new Trie();
        
        for (String word : words) {
            trie.addWord(word);
        }
        
        int nRows = board.length;
        int nCols = board[0].length;
        
        Set<String> set = new HashSet<>();
        
        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nCols; j++) {
                TrieNode p = trie.root;
                boolean[][] visited = new boolean[nRows][nCols];
                if (p.children[board[i][j] - 'a'] != null) {
                    search(i, j, board, visited, p.children[board[i][j] - 'a'], set);
                }
            }
        }
        
        return new ArrayList<>(set);
    }
    
    private void search(int row, int col, char[][] board, boolean[][] visited, TrieNode p, Set<String> res) {
        //char c = board[row][col];
        
        if (p == null) {
            return;
        }
        
        if (p.word != null) {
            res.add(p.word);
        }
        
        int[][] dirs = {{-1 ,0}, {1, 0}, {0, -1}, {0, 1}};
        int nRows = board.length;
        int nCols = board[0].length;
        
        visited[row][col] = true;
        for (int[] dir : dirs) {
            int nextRow = row + dir[0];
            int nextCol = col + dir[1];
            
            if (nextRow >= 0 && nextRow < nRows && nextCol >= 0 && nextCol < nCols && !visited[nextRow][nextCol]) {
                search(nextRow, nextCol, board, visited, p.children[board[nextRow][nextCol] - 'a'], res);
            }
        }
        
        visited[row][col] = false;
    }
}

class TrieNode {
    TrieNode[] children;
    String word;
    
    public TrieNode() {
        this.children = new TrieNode[26];
        word = null;
    }
}

class Trie {
    public TrieNode root;
    
    public Trie() {
        this.root = new TrieNode();
    }
    
    public void addWord(String word) {
        TrieNode p = root;
        
        for (char c : word.toCharArray()) {
            if (p.children[c - 'a'] == null) {
                p.children[c - 'a'] = new TrieNode();
            }
            
            p = p.children[c - 'a'];
        }
        
        p.word = word;
    }
}

Leetcode: Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Code (Java):

public class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        String delim = "[ ]+";
        s = s.replaceAll(delim, "");
        
        Stack<Integer> numStack = new Stack<Integer>();
        Stack<Character> opStack = new Stack<Character>();
        
        int result = 0;
        
        int i = 0;
        while (i < s.length()) {
            char token = s.charAt(i);
            if (isNumber(token)) {
                StringBuffer sb = new StringBuffer();
                while (i < s.length() && isNumber(s.charAt(i))) {
                    sb.append(s.charAt(i));
                    i++;
                }
                
                int val = Integer.valueOf(sb.toString());
                numStack.push(val);
            } else {
                if (opStack.isEmpty() || !hasHigherPrecedence(opStack.peek(), token)) {
                    opStack.push(token);
                    i++;
                } else {
                   calculate(numStack, opStack);
                }
            }
        }
        
        while(!opStack.isEmpty()) {
            calculate(numStack, opStack);
        }
        
        return numStack.pop();
    }
    
    private boolean isNumber(char character) {
        return character >= '0' && character <= '9';
    }
    
    private void calculate(Stack<Integer> numStack, Stack<Character> opStack) {
        int num2 = numStack.pop();
        int num1 = numStack.pop();
        char oprator = opStack.pop();
        
        int result = 0;
        
        switch(oprator) {
            case '+' : result = num1 + num2;
            break;
            
            case '-' : result = num1 - num2;
            break;
            
            case '*' : result = num1 * num2;
            break;
            
            case '/' : result = num1 / num2;
            break;
        }
        
        numStack.push(result);
    }
    
    private boolean hasHigherPrecedence(char str1, char str2) {
        if (str1 == '*'|| str1 == '/') {
            return true;
        }
        
        if ((str1 == '+' || str1 == '-') && (str2 == '+' || str2 == '-')) {
            return true;
        }
        
        return false;
    }
}

Leetcode: Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Understand the problem:
If two strings are anagram iff the sorted format is the same. 

Code (Java):

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s == null || s.length() == 0) {
            return t == null || t.length() == 0;
        }
        
        if (t == null || t.length() == 0) {
            return s == null || s.length() == 0;
        }
        
        if (s.length() != t.length()) {
            return false;
        }
        
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        
        Arrays.sort(sArr);
        Arrays.sort(tArr);
        
        for (int i = 0; i < sArr.length; i++) {
            if (sArr[i] != tArr[i]) {
                return false;
            }
        }
        
        return true;
    }
}

Leetcode: Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

Understand the problem:
The problem is a little bit hard to understand. The essence of the problem is given two strings s and t. We replace the characters in t and is able to get back the string s. Note that the mapping relationship must be 1:1 matching. e.g. 
"foo, bar" => false, because o->a and o->r, which is one to many mapping.
"bar", "foo" => false, because a->o and r->o, which is many to one mapping. 

The idea is to maintain two hash maps. One store the normal mapping between s=>t, and the other map maintains the inverse mapping from t => s. For each character, we check both maps contains the s or t. 

Code (Java):

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null || s.length() == 0) {
            return t == null || t.length() == 0;
        }
        
        if (t == null || t.length() == 0) {
            return s == null || s.length() == 0;
        }
        
        if (s.length() != t.length()) {
            return false;
        }
        
        Map<Character, Character> map = new HashMap<Character, Character>();
        Map<Character, Character> inverseMap = new HashMap<Character, Character>();
        
        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            
            if (map.containsKey(sChar) && (tChar != map.get(sChar))) {
                return false;
            }
            
            if (inverseMap.containsKey(tChar) && (sChar != inverseMap.get(tChar))) {
                return false;
            }
            
            map.put(sChar, tChar);
            inverseMap.put(tChar, sChar);
        }
        
        return true;
    }
}

Update on 1/28/16:

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if ((s == null || s.length() == 0) && (t == null || t.length() == 0)) {
            return true;
        }
        
        if ((s == null || s.length() == 0) || (t == null || t.length() == 0)) {
            return false;
        }
        
        if (s.length() != t.length()) {
            return false;
        }
        
        Map<Character, Character> forwardMap = new HashMap<>();
        Map<Character, Character> backwardMap = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            
            // Must not contain both
            if (!forwardMap.containsKey(sChar) && !backwardMap.containsKey(tChar)) {
                forwardMap.put(sChar, tChar);
                backwardMap.put(tChar, sChar);
            }
            
            // Only one contains
            if (!forwardMap.containsKey(sChar) || !backwardMap.containsKey(tChar)) {
                return false;
            }
            
            if (forwardMap.get(sChar) != tChar || backwardMap.get(tChar) != sChar) {
                return false;
            }
        }
        
        return true;
    }
}

Leetcode: Reverse Words in a String II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Could you do it in-place without allocating extra space?

Code (Java):

public class Solution {
    public void reverseWords(char[] s) {
        if (s == null || s.length <= 1) {
            return;
        }
        
        int i = 0;
        int j = s.length - 1;
        while (i < j) {
            swap(s, i, j);
            i++;
            j--;
        }
        
        // Step 2: swap again within a token
        i = 0;
        j = 0;
        while (j < s.length) {
            while (j < s.length && s[j] != ' ') {
                j++;
            }
            
            int m = i;
            int n = j - 1;
            while (m < n) {
                swap(s, m, n);
                m++;
                n--;
            }
            
            i = j + 1;
            j = i;
        }
    }
    
    private void swap(char[] s, int i, int j) {
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }
}

Leetcode: Read N Characters Given Read4 – Call multiple times

Question:
Similar to Question [15. Read N Characters Given Read4], but the read function may be
called multiple times.

Solution:
This makes the problem a lot more complicated, because it can be called multiple times
and involves storing states.

Therefore, we design the following class member variables to store the states:
i. buffer – An array of size 4 use to store data returned by read4 temporarily. If
the characters were read into the buffer and were not used partially, they will
be used in the next call.

ii. offset – Use to keep track of the offset index where the data begins in the next
read call. The buffer could be read partially (due to constraints of reading up
to n bytes) and therefore leaving some data behind.

iii. bufsize – The real buffer size that stores the actual data. If bufsize > 0, that
means there is partial data left in buffer from the last read call and we should
consume it before calling read4 again. On the other hand, if bufsize == 0, it
means there is no data left in buffer.

This problem is a very good coding exercise. Coding it correctly is extremely tricky due

to the amount of edge cases to consider.

Code (Java):

/* The read4 API is defined in the parent class Reader4.
int read4(char[] buf); */
public class Solution extends Reader4 {
    private char[] buffer = new char[4];
    int offset = 0, bufsize = 0;
/**
* @param buf Destination buffer
* @param n   Maximum number of characters to read
* @return    The number of characters read
*/
    public int read(char[] buf, int n) {
        int readBytes = 0;
        boolean eof = false;
        while (!eof && readBytes < n) {
            int sz = (bufsize > 0) ? bufsize : read4(buffer);
            if (bufsize == 0 && sz < 4) eof = true;
            int bytes = Math.min(n - readBytes, sz);
            System.arraycopy(buffer /* src */, offset /* srcPos */, buf /* dest */, 
                readBytes /* destPos */, bytes /* length */);
            offset = (offset + bytes) % 4;
            bufsize = sz - bytes;
            readBytes += bytes;
        }
        return readBytes;
    }
}

Summary:
This problem is not very hard, but requires thinking of every corner cases. To sum up, the key of the problem is to put the char buf4[4] into global, and maintains two more global variables: 
 -- offset : the starting position in the buf4 that a read() should start from. 
 -- bytesLeftInBuf4 : how many elements left in the buf4. 

One corner case to consider is when is the eof should be true? In the previous question, it is true only if bytesFromRead4 < 4. However, in this question, since we might have some bytes left the buf4, even if it is not end of the file, we may mistakely consider the eof as true. So the condition to set eof is true is bytesFromRead4 < 4 && bytesLeftInBuf4 == 0 

Another corner case we need to consider is: if the bytesFromRead4 + bytesRead > n, the actual bytes to copy is n - bytesRead. 
For example, the file is "abcde", and read(2), in this case, the bytesFromRead4 = 4, but we should only copy 2 bytes from the buf4. So be very careful about this case. 

At the end, we need to update the global offset and bytesLeftInBuf4, as well as the local bytesRead. 

Do execrise more about this question, this is really classical. 


Update on 11/19/18:

/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); */

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    boolean m_fEof = false;
    char[] m_buf4 = new char[4];
    int m_lastPos = 0;
    int m_cBytesLastRead = 0;
    
    public int read(char[] buf, int n) {        
        int curPos = 0;
        while (curPos < n) {
            if (m_lastPos == m_cBytesLastRead) {
                m_cBytesLastRead = read4(m_buf4);
                if (m_cBytesLastRead < 4) {
                    m_fEof = true;
                }
                m_lastPos = 0;
            }
            
            int cBytesToRead = Math.min(n - curPos, m_cBytesLastRead - m_lastPos);
            System.arraycopy(m_buf4, m_lastPos, buf, curPos, cBytesToRead);
            
            curPos += cBytesToRead;
            m_lastPos += cBytesToRead;
            
            if (m_fEof) {
                break;
            }
        }
        
        return curPos;
    }
}

Leetcode: Read N Characters Given Read4

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function will only be called once for each test case.

Understand the problem:
This seemingly easy coding question has some tricky edge cases. When read4 returns
less than 4, we know it must reached the end of file. However, take note that read4
returning 4 could mean the last 4 bytes of the file.

To make sure that the buffer is not copied more than n bytes, copy the remaining bytes
(n – readBytes) or the number of bytes read, whichever is smaller.

Code (Java):

/** The read4 API is defined in the parent class Reader4. int read4(char[] buf); */

public class Solution extends Reader4 {
/**
* @param buf 　Destination buffer
* @param n　　　Maximum number of characters to read
* @return　    The number of characters read
*/
    public int read(char[] buf, int n) {
        char[] buffer = new char[4];
        int readBytes = 0;
        boolean eof = false;
        while (!eof && readBytes < n) {
            int sz = read4(buffer);
            if (sz < 4) eof = true;
            int bytes = Math.min(n - readBytes, sz);
            System.arraycopy(buffer /* src */, 0 /* srcPos */,　buf /* dest */, readBytes /* destPos */, bytes /* length */);
            readBytes += bytes;
        }
        return readBytes;
    }
}

Update on 9/29/15:

/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); */

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    public int read(char[] buf, int n) {
        boolean eof = false;
        int charsRead = 0;
        char[] buf4 = new char[4];
        
        while (!eof && charsRead < n) {
            int size = read4(buf4);
            if (size < 4) {
                eof = true;
            }
            
            if (charsRead + size > n) {
                size = n - charsRead;
            }
            
            System.arraycopy(buf4, 0, buf, charsRead, size);
            charsRead += size;
        }
        
        return charsRead;
    }
}