291. Word Pattern II

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 substring in str.

Examples:

1. pattern = "abab", str = "redblueredblue" should return true.
2. pattern = "aaaa", str = "asdasdasdasd" should return true.
3. pattern = "aabb", str = "xyzabcxzyabc" should return false.

Notes:
You may assume both pattern and str contains only lowercase letters.

Solution:

We use DFS + backtracking to check if the substring of pattern can be used to match there previous pattern.

In the recursion, we check if the current character has already had a mapping.

If so, we check if it can go along with this path to the end.

Otherwise, we use backtracking to put all candidate mapping of this character and check if it has its path to the end.

The end condition is that when we finish putting all character in the pattern string to the HashMap, we check if the target string has also been finished putting all its elements.



Code:

public class Solution {
    
    public HashMap<Character, String> map = new HashMap<>();
    public boolean wordPatternMatch(String pattern, String str) {
        if (pattern.length() == 0) {
            return str.length() == 0;
        }
        char c = pattern.charAt(0);
        if (map.containsKey(c)) {
            String value = map.get(c);
            if (value.length() > str.length() || !str.substring(0, value.length()).equals(value)) {
                return false;
            }
            if (wordPatternMatch(pattern.substring(1), str.substring(value.length()))) {
                return true;
            }
        }
        else {
            for (int i = 1; i <= str.length(); i++) {
                String value = str.substring(0, i);
                if (map.containsValue(value)) {
                    continue;
                }
                map.put(c, value);
                if (wordPatternMatch(pattern.substring(1), str.substring(value.length()))) {
                    return true;
                }
                map.remove(c);
            }
        }
        return false;
    }
}

290. 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:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Solution:

The idea is to create two HashMaps.

We first check the uniqueness between each character in the pattern to words in string using one HashMap.

Then we check the uniqueness between each words in the string to the character in the pattern using the second HashMap.

The reason to check twice is to handle such case:

"abcb" -> "dog cat dog cat"



Code:

public class Solution {
    public boolean wordPattern(String pattern, String str) {
        HashMap<Character, String> map1 = new HashMap<>();
        String[] strarr = str.split(" ");
        if (strarr.length != pattern.length()) {
            return false;
        }
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (!map1.containsKey(c)) {
                map1.put(c, strarr[i]);
            }
            else {
                if (!map1.get(c).equals(strarr[i])) {
                    return false;
                }
            }
        }
        HashMap<String, Character> map2 = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (!map2.containsKey(strarr[i])) {
                map2.put(strarr[i], c);
            }
            else {
                if (map2.get(strarr[i]) != c) {
                    return false;
                }
            }
        }
        return true;
    }
}

37. Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.



Solution:

Use DFS and backtracking to fill each grid with a valid answer.



Code:

public class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length != 9) {
            return;
        }
        if (board[0] == null || board[0].length != 9) {
            return;
        }
        helper(board);
    }
    
    public boolean helper(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    continue;
                }
                for (char num = '1'; num <= '9'; num++) {
                    board[i][j] = num;
                    if (isValid(board) && helper(board)) {
                        return true;
                    }
                    board[i][j] = '.';
                }
                return false;
            }
        }
        return true;
    }
    
    public boolean isValid(char[][] board) {
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear();
        }
        for (int j = 0; j < 9; j++) {
            for (int i = 0; i < 9; i++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear();
        }
        for (int k = 0; k < 9; k++) {
            for (int i = k / 3 * 3; i < k / 3 * 3 + 3; i++) {
                for (int j = (k % 3) * 3; j < (k % 3) * 3 + 3; j++) {
                    if (board[i][j] == '.') {
                        continue;
                    }
                    if (set.contains(board[i][j])) {
                        return false;
                    }
                    set.add(board[i][j]);
                }
            }
            set.clear();
        }
        return true;
    }
}

36. Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Solution:

For this kind of problems, you have to go through the entire grid to check each entry.

We first check each row.

Secondly we check each column.

Finally we check each 3 x 3 grid. We can use / and % to locate the coordinates of sub grid.

The time complexity is O(1) and the space complexity is O(1), since the number of input is constant.



Code:

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length != 9) {
            return false;
        }
        if (board[0] == null || board[0].length != 9) {
            return false;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear();
        }
        for (int j = 0; j < 9; j++) {
            for (int i = 0; i < 9; i++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear();
        }
        for (int k = 0; k < 9; k++) {
            for (int i = k / 3 * 3; i < k / 3 * 3 + 3; i++) {
                for (int j = (k % 3) * 3; j < (k % 3) * 3 + 3; j++) {
                    if (board[i][j] == '.') {
                        continue;
                    }
                    if (set.contains(board[i][j])) {
                        return false;
                    }
                    set.add(board[i][j]);
                }
            }
            set.clear();
        }
        return true;
    }
}

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution:

We use DFS to find all possible solutions.

The rule we need to follow is:

1. number of "(" should < n, we can add a "(".

2. number of ")" should < number of "(", we can add a ")".



Code:

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        helper(result, "", 0, 0, n);
        return result;
    }
    
    public void helper(List<String> result, String path, int left, int right, int count) {
        if (path.length() == count * 2) {
            result.add(path);
            return;
        }
        if (left < count) {
            helper(result, path + "(", left + 1, right, count);
        }
        if (right < left) {
            helper(result, path + ")", left, right + 1, count);
        }
    }
}

140. Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution:

We use DFS + memorization to solve this problem.

For a giving string s, we can break it into two half: s.substring(0, i) and s.substring(i).

If s.substring(i) is in the dictionary, we can:

1. Break s.substring(0, i). Let's say the result is tmp (all possible combinations).

2. For each combination comb in tmp, we create comb + " " + s.substring(i), to form a valid combination of s, and add it to the result list.

After dealing with the current string s, don't forget to add its results to the HashMap such that we do not need to calculate it again.



Code:

public class Solution {
    
    public HashMap<String, List<String>> map = new HashMap<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> res = new ArrayList<>();
        if (map.containsKey(s)) {
            return map.get(s);
        }
        if (wordDict.contains(s)) {
            res.add(s);    
        }
        for (int i = 1; i < s.length(); i++) {
            String suffix = s.substring(i);
            if (wordDict.contains(suffix)) {
                List<String> list = wordBreak(s.substring(0, i), wordDict);
                for (String str : list) {
                    res.add(str + " " + suffix);
                }
            }
        }
        map.put(s, res);
        return res;
    }
}

39. Combination Sum

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. 

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7, 
A solution set is: 

[
  [7],
  [2, 2, 3]
]

Solution:

Use DFS to traverse all combinations and check if the sum is target.

To remove duplicates, we first sort the array.

In the DFS function, when we find a number equals to its previous one but the previous one has not been selected, we cannot select this number.



Code:

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return result;
        }
        Arrays.sort(candidates);
        helper(candidates, target, result, new ArrayList<Integer>(), 0);
        return result;
    }
    
    public void helper(int[] nums, int target, List<List<Integer>> result, List<Integer> list, int pos) {
        if (target == 0) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
        if (target < 0) {
            return;
        }
        for (int i = pos; i < nums.length; i++) {
            if (i != pos && nums[i] == nums[i - 1]) {
                continue;
            }
            list.add(nums[i]);
            helper(nums, target - nums[i], result, list, i);
            list.remove(list.size() - 1);
        }
    }
}

10. Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Solution:

Method 1: DP

We use dynamic programming to determine whether s and p are match.

boolean match[i][j]: whether the first i characters in s match the first j characters in p.

There are two cases to consider:

1. s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j) == '.'.

match[i - 1][j - 1]

2. p.charAt(j) == '*'
 
a). match[i][j - 2], 0 occurrence of p.charAt(j - 1)
      or
b). match[i - 1][j], if s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.'.

The time complexity is O(mn) and the space complexity is O(mn) as well.



Code:

public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] match = new boolean[s.length() + 1][p.length() + 1];
        match[0][0] = true;
        
        // deal with a*, a*b*, a*b*c*...
        for (int i = 1; i < match[0].length; i++) {
            if (p.charAt(i - 1) == '*') {
                match[0][i] = match[0][i - 2];
            }
        }
        for (int i = 1; i < match.length; i++) {
            for (int j = 1; j < match[0].length; j++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    match[i][j] = match[i - 1][j - 1];
                }
                else if (p.charAt(j - 1) == '*') {
                    
                    // s: x   p xa*, we check a* is empty, which is match[i][j - 2];
                    match[i][j] = match[i][j - 2];
                    
                    // s: xa  p: xa* -> a is part of a*, so we check s: x  p: xa*, which is match[i - 1][j]
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        match[i][j] = match[i][j] || match[i - 1][j];
                    }
                }
                else {
                    match[i][j] = false;
                }
            }
        }
        return match[s.length()][p.length()];
    }
}

Method 2: Optimization (Rolling Array)

We need to update match[i % 2][0] in the j loop.



Code:

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] match = new boolean[2][n + 1];
        match[0][0] = true;
        
        // p: a*, a*b*, a*b*c*...
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                match[0][j] = match[0][j - 2];
            }
        }
        
        for (int i = 1; i <= m; i++) {
            match[i % 2][0] = false;
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    match[i % 2][j] = match[(i - 1) % 2][j - 1];
                }
                else if (p.charAt(j - 1) == '*') {
                    // s: x  p: xa*
                    match[i % 2][j] = match[i % 2][j - 2];
                    
                    // s: xa  p: xa*  p: x.*
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        match[i % 2][j] = match[i % 2][j] || match[(i - 1) % 2][j];
                    }
                }
                else {
                    match[i % 2][j] = false;
                }
                
            }
        }
        
        return match[m % 2][n];
    }
}

78. Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution:

Method 1: DFS

Use DFS to traverse all possible combinations and store all of them into results.

To keep the subsets in order, we first sort the input array.



Code:

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        helper(nums, result, new ArrayList<Integer>(), 0);
        return result;
    }
    
    public void helper(int[] nums, List<List<Integer>> result, List<Integer> list, int pos) {
        result.add(new ArrayList<Integer>(list));
        
        for (int i = pos; i < nums.length; i++) {
            list.add(nums[i]);
            helper(nums, result, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

Method 2: Bitset

76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution:

Method 1:

1. Use two pointers start and end to keep track of the minimum window that satisfy the condition.

2. Move end to find a valid window.

3. If we find a valid window, move start to find a smaller window.



Code:

public class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, 0);
        }
        for (char c : t.toCharArray()) {
            if (!map.containsKey(c)) {
                map.put(c, 1);
            }
            else {
                map.put(c, map.get(c) + 1);
            }
        }
        
        int start = 0;
        int end = 0;
        int minStart = 0;
        int minLen = Integer.MAX_VALUE;
        int count = t.length();
        while (end < s.length()) {
            char c1 = s.charAt(end);
            if (map.get(c1) > 0) {
                count--;
            }
            map.put(c1, map.get(c1) - 1);
            end++;
            
            while (count == 0) {
                if (end - start < minLen) {
                    minLen = end - start;
                    minStart = start;
                }
                
                char c2 = s.charAt(start);
                map.put(c2, map.get(c2) + 1);
                if (map.get(c2) > 0) {
                    count++;
                }
                
                start++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }
}

Method 2:


Code:

public class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            if (!map.containsKey(c)) {
                map.put(c, 1);
            }
            else {
                map.put(c, map.get(c) + 1);
            }
        }
        int len = Integer.MAX_VALUE;
        int head = 0;
        int start = 0; 
        int end = 0;
        int count = map.size();
        while (end < s.length()) {
            char c = s.charAt(end);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                if (map.get(c) == 0) {
                    count--;
                }
            }
            end++;
            while (count == 0) {
                if (end - start < len) {
                    len = end - start;
                    head = start;
                }
                char ch = s.charAt(start);
                if (map.containsKey(ch)) {
                    map.put(ch, map.get(ch) + 1);
                    if (map.get(ch) > 0) {
                        count++;
                    }
                }
                start++;
            }
        }
        if (len == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(head, head + len);
    }
}

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.



Solution:

Method 1: Heap

Use a min-heap to store the head of all lists.

While the heap is not empty, we poll the smallest node and add it to the merged list.

If this node has next, we add its next to the heap.

The time complexity is O(nlogk) and the space complexity is O(k).



Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
            public int compare(ListNode x, ListNode y) {
                return x.val - y.val;
            }
        });
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                heap.offer(lists[i]);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            if (node.next != null) {
                heap.offer(node.next);
            }
            tail.next = node;
            tail = node;
        }
        return dummy.next;
    }
}

Method 2:

Method 3:

33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Solution:

The idea is use binary search to find the target.

When we have mid, we check:

1. If nums[start] < nums[mid]

  a). target >= nums[start] && target < nums[mid]. ==> search from start to mid.

  b). target < nums[start] || target >= nums[mid]. ==> search from mid to end (still a rotated sorted array)

2. If nums[start] >= nums[mid]

  a).  target > nums[mid] && target <= nums[end]. ==> search from mid to end.

  b). target <= nums[mid] || target > nums[end]. ==> search from start to mid. (still a rotated sorted array)

Thus, the time complexity is still O(logn).



Code:

public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[start] < nums[mid]) {
                if (target >= nums[start] && target < nums[mid]) {
                    end = mid;
                }
                else {
                    start = mid;
                }
            }
            else {
                if (target > nums[mid] && target <= nums[end]) {
                    start = mid;
                }
                else {
                    end = mid;
                }
            }
        }
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}