Showing posts with label Twitter. Show all posts
Showing posts with label Twitter. Show all posts

Saturday, June 10, 2017

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;
    }
}

Tuesday, June 6, 2017

218. The Skyline Problem

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skylineformed by these buildings collectively (Figure B).
BuildingsSkyline Contour
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
Notes:
  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li. 
  • The output list must be sorted by the x position. 
  • There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]



Solution:

1. Create height coordinates. We use negative value to denote a start point, and positive value to denote an end point.

2. Sort the heights. 3 corner cases: same start, same end, and end == start.

3. Create a max heap with initial value 0.

4. Go through the heights.

a). If it is a start point, put it into the heap. If the top of heap changes, this point with the new heap value (itself) should be in the final result.

b). If it is an end point,  remove it from the heap. If the top of heap changes, this point with the new heap top value should be in the final result.

Detailed explanation check out this Youtube Video.

TreeMap support O(logn) on insert and remove operation.

The time complexity is O(nlogn) and the space complexity is O(n).



Code:


public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> heights = new ArrayList<>();
        for (int[] building : buildings) {
            heights.add(new int[] {building[0], -building[2]});
            heights.add(new int[] {building[1], building[2]});
        }
        Collections.sort(heights, new Comparator<int[]>() {
            public int compare(int[] x, int[] y) {
                if (x[0] == y[0]) {
                    return x[1] - y[1];
                }
                return x[0] - y[0];
            }
        });
        List<int[]> result = new ArrayList<>();
        TreeMap<Integer, Integer> map = new TreeMap<>(Collections.reverseOrder());
        map.put(0, 1);
        int prevHeight = 0;
        for (int[] height : heights) {
            if (height[1] < 0) {
                Integer count = map.get(-height[1]);
                count = count == null ? 1 : count + 1;
                // Use a count to store the frequency of this height.
                // The reason is that map cannot store duplicate items.
                map.put(-height[1], count);
            }
            else {
                Integer count = map.get(height[1]);
                if (count == 1) {
                    map.remove(height[1]);
                }
                else {
                    map.put(height[1], count - 1);
                }
            }
            int currHeight = map.firstKey();
            if (currHeight != prevHeight) {
                result.add(new int[] {height[0], currHeight});
                prevHeight = currHeight;
            }
        }
        return result;
    }
}




public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<>();
        List<int[]> heights = new ArrayList<>();
        for (int[] building : buildings) {
            heights.add(new int[] {building[0], -building[2]});
            heights.add(new int[] {building[1], building[2]});
        }
        Collections.sort(heights, new Comparator<int[]>() {
            public int compare(int[] x, int[] y) {
                if(x[0] == y[0]) {
                    return x[1] - y[1];
                }
                return x[0] - y[0];
            }    
        });
        Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(0);
        int prev = 0;
        for (int[] height : heights) {
            if (height[1] < 0) {
                maxHeap.offer(-height[1]);
            }
            else {
                maxHeap.remove(height[1]);
            }
            int curr = maxHeap.peek();
            if (curr != prev) {
                result.add(new int[] {height[0], curr});
                prev = curr;
            }
        }
        return result;
    }
}

Monday, June 5, 2017

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];
    }
}

Monday, May 29, 2017

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:

Sunday, May 28, 2017

44. Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

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", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false



Solution:

Method 1: Two Pointers

We use two pointers.

One points to the string and one points to the pattern.

When we find a '?' in the pattern, we advance two pointers.

When we find a '*' in the pattern, we mark the current index of the string and the current index of the '*'. And start to do the match from mark and star + 1.

If we cannot find match, we go back to mark + 1 and star + 1 and try to match. (Every time we backtrack, we need to increase mark by 1.)

Worst case time complexity is O(mn).

The space complexity is O(1).



Code:


public class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0;
        int j = 0;
        int mark = 0;
        int star = -1;
        while (i < s.length()) {
            if (j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
                i++;
                j++;
            }
            else if (j < p.length() && p.charAt(j) == '*') {
                mark = i;
                star = j;
                j++;
            }
            else if (star != -1) {
                mark++;
                i = mark;
                j = star + 1;
            }
            else {
                return false;
            }
        }
        while (j < p.length() && p.charAt(j) == '*') {
            j++;
        }
        return j == p.length();
    }
}



Method 2: Dynamic Programming


Code:


269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Example 1:
Given the following words in dictionary,
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
The correct order is: "wertf".
Example 2:
Given the following words in dictionary,
[
  "z",
  "x"
]
The correct order is: "zx".
Example 3:
Given the following words in dictionary,
[
  "z",
  "x",
  "z"
]
The order is invalid, so return "".
Note:
  1. You may assume all letters are in lowercase.
  2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
  3. If the order is invalid, return an empty string.
  4. There may be multiple valid order of letters, return any one of them is fine.



Solution:

The idea is to use topological sort to get the order of characters.

To build the graph, we compare every two adjacent words.

If we found the character in the same index different, we know the order of these two characters, and thus add an edge and update the indegree.

After building the graph, we simply apply topological sort.



Code:


public class Solution {
    public String alienOrder(String[] words) {
        ArrayList<Character>[] adj = new ArrayList[26];
        int[] indegree = new int[26];
        Arrays.fill(indegree, -1);
        
        for (int i = 0; i < 26; i++) {
            adj[i] = new ArrayList<Character>();
        }
        
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                if (indegree[c - 'a'] < 0) {
                    indegree[c - 'a'] = 0;
                }
            }
            if (i == 0) {
                continue;
            }
            String w1 = words[i - 1];
            String w2 = words[i];
            int len = Math.min(w1.length(), w2.length());
            for (int j = 0; j < len; j++) {
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 == c2) {
                    if (j == w2.length() - 1 && w1.length() > w2.length()) {
                        return "";
                    }
                    continue;
                }
                if (!adj[c1 - 'a'].contains(c2)) {
                    adj[c1 - 'a'].add(c2);
                    indegree[c2 - 'a']++;
                }
                break;
            }
        }
        
        Queue<Character> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (indegree[i] == 0) {
                queue.offer((char)('a' + i));
            }
        }
        while (!queue.isEmpty()) {
            char c = queue.poll();
            sb.append(c);
            for (char nei : adj[c - 'a']) {
                indegree[nei - 'a']--;
                if (indegree[nei - 'a'] == 0) {
                    queue.offer(nei);
                }
            }
        }
        for (int d : indegree) {
            if (d > 0) {
                return "";
            }
        }
        return sb.toString();
    }
}



Use HashMap


public class Solution {
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }
        StringBuilder order = new StringBuilder();
        HashMap<Character, HashSet<Character>> adj = new HashMap<>();
        for (char c = 'a'; c <= 'z'; c++) {
            adj.put(c, new HashSet<Character>());
        }
        int[] degree = new int[26];
        Arrays.fill(degree, -1);
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                if (degree[c - 'a'] == -1) {
                    degree[c - 'a'] = 0;
                }
            }
            if (i == 0) {
                continue;
            }
            String w1 = words[i - 1];
            String w2 = words[i];
            int len = Math.min(w1.length(), w2.length());
            for (int j = 0; j < len; j++) {
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 != c2) {
                    if (!adj.get(c1).contains(c2)) {
                        adj.get(c1).add(c2);
                        degree[c2 - 'a']++;  
                    }
                    break;
                }
                if (j == w2.length() - 1 && w1.length() > w2.length()) {
                    return "";
                }
            }
        }
        Queue<Character> queue = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if (degree[i] == 0) {
                queue.offer((char)(i + 'a'));
            }
        }
        while (!queue.isEmpty()) {
            char c = queue.poll();
            order.append(c);
            for (char nei : adj.get(c)) {
                if (--degree[nei - 'a'] == 0) {
                    queue.offer(nei);
                }
            }
        }
        for (int i = 0; i < 26; i++) {
            if (degree[i] > 0) {
                return "";
            }
        }
        return order.toString();
    }
}

Saturday, May 27, 2017

380. Insert Delete GetRandom O(1)

Design a data structure that supports all following operations in average O(1) time.
  1. insert(val): Inserts an item val to the set if not already present.
  2. remove(val): Removes an item val from the set if present.
  3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();



Solution:

Use a HashMap and an ArrayList.

ArrayList is to store the elements and the HashMap is to mapping the position of the element.

To insert an element, simply check if its already in the map. If not, we append it to the ArrayList and update the HashMap.

To remove an element, we use HashMap to find its location, swap with the end of the ArrayList, and remove it. Don't forget to update the mapping of the end element which swapped location.



Code:


public class RandomizedSet {

    ArrayList<Integer> list;
    HashMap<Integer, Integer> map;
    java.util.Random rand = new java.util.Random();
    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int key = list.get(list.size() - 1);
        int index = map.get(val);
        Collections.swap(list, index, list.size() - 1);
        map.put(key, index);
        map.remove(list.get(list.size() - 1));
        list.remove(list.size() - 1);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        return list.get(rand.nextInt(list.size())); 
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

Friday, May 26, 2017

43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:
  1. The length of both num1 and num2 is < 110.
  2. Both num1 and num2 contains only digits 0-9.
  3. Both num1 and num2 does not contain any leading zero.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.



Solution:


We can split this process to:

1. multiply num1.charAt(i) and num2.charAt(j). Put the result in product[i + j + 1].

2. calculate carry and complete the multiplication.

3. output



Code:


public class Solution {
    public String multiply(String num1, String num2) {
        int n1 = num1.length();
        int n2 = num2.length();
        int[] product = new int[n1 + n2];
        for (int i = n1 - 1; i >= 0; i--) {
            for (int j = n2 - 1; j >= 0; j--) {
                product[i + j + 1] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            }
        }
        int carry = 0;
        for (int i = n1 + n2 - 1; i >= 0; i--) {
            int sum = (product[i] + carry) % 10;
            carry = (product[i] + carry) / 10;
            product[i] = sum;
        }
        StringBuilder sb = new StringBuilder();
        for (int num : product) {
            sb.append(num);
        }
        while (sb.length() != 0 && sb.charAt(0) == '0') {
            sb.deleteCharAt(0);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

341. Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1:
Given the list [[1,1],2,[1,1]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Given the list [1,[4,[6]]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].



Solution:

We push all elements into a stack in reverse order such that when we pop, it's in normal order. (1)

When we check hasNext, we first peek the top element and check if it is an integer.

If it is an integer, we simply return true and next() can pop it.

If it is a list, we do (1) again.

For example, the input is [1, [2, [3]]].

After we push into the stack, it looks like
1
[2, [3]]

After one next(), we pop up 1.

When we call hasNext(), since the stack only has [2, [3]], we do (1) and the stack becomes
2
[3]



Code:


/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {

    private Stack<NestedInteger> stack = new Stack<>();
    
    public NestedIterator(List<NestedInteger> nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        hasNext();
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            NestedInteger curr = stack.peek();
            if (curr.isInteger()) {
                return true;
            }
            stack.pop();
            for (int i = curr.getList().size() - 1; i >= 0; i--) {
                stack.push(curr.getList().get(i));
            }
        }
        return false;
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */