Day: February 15, 2018

Written by Bilbo

Minimum Window Substring

  General Framework to Solve Substring Problems Given a string and need to find a substring of it which satisfy some restrictions. A general way is to use a hashmap assisted with two pointers. https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-‘substring’-problems Minimum Window Substring (Framework Solution) This is the “substring framework” solution. Core idea is that when each time end pointer […]

Written by Bilbo

Merge Intervals

Merge Intervals First sort the intervals based on starting point. (Using Collections.sort(intervals, new Comparator() { @Override public int compare(Interval i1, Interval i2) { return i1.start – i2.start; } });). Then walk through the intervals and either insert a new one or merge with previous one. Time: O(nlogn), sorting. Note that timing is worse if merge […]