Search

Zhiwen's study blog

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.

Show Company Tags
Show Tags
Show Similar Problems
public class Solution {
    private List<String> result = new ArrayList<>();
    private int maxLen = 0; 
    private StringBuilder sb = new StringBuilder();
    
    public List<String> wordBreak(String s, List<String> wordDict) {
        if (s == null || wordDict == null) return result;
        if (!canBreak(s, wordDict)) return result;
        helper(s, 0, wordDict);
        return result;
    }
    
    private boolean canBreak(String s, List<String> wordDict) {
        for (String word : wordDict) maxLen = Math.max(word.length(), maxLen);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        // Should allow i = s.length()
        for (int i = 1; i <= s.length(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (i - j > maxLen) {
                    dp[i] = false;
                    break;
                }
                String temp = s.substring(j, i);
                if (dp[j] && wordDict.contains(temp)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
    
    private void helper(String s, int start, List<String> wordDict) {
        if (start == s.length()) {
            result.add(sb.substring(0, sb.length() - 1));
            return;
        }
        // Should allow i == s.length()
        for (int i = start + 1; i <= s.length(); i++) {
            if (i - start > maxLen) {
                return;
            }
            String temp = s.substring(start, i);
            if (wordDict.contains(temp)) {
                int len1 = sb.length();
                sb.append(temp + " ");
                int len2 = sb.length();
                // New recursion start from i, not i + 1;
                helper(s, i, wordDict);
                sb.delete(len1, len2);
            }
        }
    }
}

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <= 1) return intervals;
        List<Interval> result = new ArrayList<>();
        // Collections.sort(intervals, new Comparator<Interval>() {
        //     @Override
        //     public int compare(Interval i1, Interval i2) {
        //         return i1.start - i2.start;
        //     }
        // });
        intervals.sort((i1, i2) -> i1.start - i2.start);

        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (Interval interval : intervals) {
            if (interval.start <= end) {
                // merge
                end = Math.max(end, interval.end);
            } else {
                // add to result;
                result.add(new Interval(start, end));
                start = interval.start;
                end = interval.end;
            }
        }
        result.add(new Interval(start, end));
        return result;
    }
}

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (!map.containsKey(num)) {
                map.put(num, 1);
            } else {
                map.put(num, map.get(num) + 1);
            }
        }
        
        List<Integer>[] bucket = new List[nums.length + 1];
        for (int key : map.keySet()) {
            if (bucket[map.get(key)] == null) {
                bucket[map.get(key)] = new ArrayList<>();
            }
            bucket[map.get(key)].add(key);
        }
        
        List<Integer> result = new ArrayList<>();
        for (int i = bucket.length - 1; i >= 0; i--) {
            if (result.size() >= k) {
                return result;
            }
            if (bucket[i] != null) {
                result.addAll(bucket[i]);
            }
        }
        return result;
    }
}

50. Pow(x, n)

Implement pow(x, n).

public class Solution {
public double myPow(double x, int n) {
if (n == Integer.MIN_VALUE) return myPow(x, n + 1) / x;
if (n < 0) return 1.0 / myPow(x, -n);
if (n == 0) return 1.0;
if (n == 1) return x;
double temp = myPow(x, n / 2);
if (n % 2 == 1) {
return x * temp * temp;
} else {
return temp * temp;
}
}
}
[java]

145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode runner = root;
        while (runner != null) {
            stack.push(runner);
            runner = runner.left;
        }
        // Use child to keep track of whether node have been visited.
        TreeNode child = null;
        while (!stack.isEmpty()) {
            TreeNode cur = stack.peek();
            // If no right child or right child has been visited
            if (cur.right == null || cur.right == child) {
                result.add(stack.pop().val);
                child = cur;
            } else {
                // Continue to push left child of the new node.
                cur = cur.right;
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
            }
        }
        return result;
    }
}

reference:
http://rleetcode.blogspot.com/2014/06/binary-tree-postorder-traversal.html

124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    // Should use private, and declare maxSum as global variable.
    private int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return maxSum;
    }
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int max = root.val;
        int l = helper(root.left);
        int r = helper(root.right);
        if (l > 0) max += l;
        if (r > 0) max += r;
        maxSum = Math.max(maxSum, max);
        if (l > 0 || r > 0) return root.val + Math.max(l, r);
        return root.val;
    }
}

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Show Company Tags
Show Tags
Show Similar Problems
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        /*
        Solution 1: Space O(n)
        if (root == null || p == root || q == root) {
            return root;
        }
        
        // Devide
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // Conquer
        if (left != null && right != null) {
            return root;
        } else if (left == null) {
            return right;
        } else {
            return left;
        }
        */
        // Solution 2: Space O(1), since it's a binary search tree.
        if (root == null || p == null || q == null) {
            return root;
        }
        
        TreeNode node = root;
        
        if (p.val < root.val && q.val < root.val) {
            node = lowestCommonAncestor(root.left, p, q);
        }
        if (p.val > root.val && q.val > root.val) {
            node = lowestCommonAncestor(root.right, p, q);
        }
        
        return node;
    }
}

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Show Company Tags
Show Tags
Show Similar Problems
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);
        if (l != null && r != null) return root;
        if (l != null) return l;
        if (r != null) return r;
        // Need to have a return statement here.
        return null;
    }
}

117. Populating Next Right Pointers in Each Node II

Follow up for problem “Populating Next Right Pointers in Each Node“.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

  • You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL
/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        Queue<TreeLinkNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            TreeLinkNode pre = null;
            TreeLinkNode cur;
            for (int i = 0; i < size; i++) {
                cur = q.poll();
                if (pre != null) pre.next = cur;
                pre = cur;
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
        }
    }
}

Create a free website or blog at WordPress.com.

Up ↑