Sept. 30, 2017, Saturday

 BLANK

1. Complex String manipulation
2. Math

1. Complex String manipulation

224. Basic Calculator

只有加减,括号,没有负数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public static int calculate(String s) {
        int len = s.length(), sign = 1, result = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < len; i++) {
            if (Character.isDigit(s.charAt(i))) {
                int sum = s.charAt(i) - '0';
                while (i + 1 < len && Character.isDigit(s.charAt(i + 1))) {
                    sum = sum * 10 + s.charAt(i + 1) - '0';
                    i++;
                }
                result += sum * sign;
            } else if (s.charAt(i) == '+')
                sign = 1;
            else if (s.charAt(i) == '-')
                sign = -1;
            else if (s.charAt(i) == '(') {
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1;
            } else if (s.charAt(i) == ')') {
                result = result * stack.pop() + stack.pop();
            }
 
        }
        return result;
    }
}

227. Basic Calculator II

只有加减乘除,没有负数,括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public int calculate(String s) {
    int len;
    if(s==null || (len = s.length())==0) return 0;
    Stack<Integer> stack = new Stack<Integer>();
    int num = 0;
    char sign = '+';
    for(int i=0;i<len;i++){
        if(Character.isDigit(s.charAt(i))){
            num = num*10+s.charAt(i)-'0';
        }
        if((!Character.isDigit(s.charAt(i)) &&' '!=s.charAt(i)) || i==len-1){
            if(sign=='-'){
                stack.push(-num);
            }
            if(sign=='+'){
                stack.push(num);
            }
            if(sign=='*'){
                stack.push(stack.pop()*num);
            }
            if(sign=='/'){
                stack.push(stack.pop()/num);
            }
            sign = s.charAt(i);
            num = 0;
        }
    }
 
    int re = 0;
    for(int i:stack){
        re += i;
    }
    return re;
}

2. Math

233. Number of Digit One

1
2
3
4
5
6
7
8
9
10
public int countDigitOne(int n) {
    int ones = 0, m = 1, r = 1;
    while (n > 0) {
        ones += (n + 8) / 10 * m + (n % 10 == 1 ? r : 0);
        r += n % 10 * m;
        m *= 10;
        n /= 10;
    }
    return ones;
}

Sept. 29, 2017, Friday

 BLANK

1. DP
2.
3.
4.

1. DP

221. Maximal Square

Naive Method

时间复杂度O(n^2) 空间复杂度O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix.length == 0)return 0;
        int len1 = matrix.length;
        int len2 = matrix[0].length;
        int[][] table = new int[len1+1][len2+1];
        int max = 0;
        for(int i =1; i<=len1; i++){
            for(int j=1; j<=len2; j++){
                if(matrix[i-1][j-1] =='0'){
                    table[i][j] = 0;
                }else{
                    table[i][j] = Math.min(table[i-1][j-1],Math.min(table[i-1][j], table[i][j-1])) +1;
                }
                max =Math.max(max, table[i][j]);
            }
        }
        return max * max;
 
    }
}

Revised Method

时间复杂度O(n^2) 空间复杂度O(n)
即使存在覆盖,部分情况下,也可以实现降维度的table。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
        int[] dp = new int[cols + 1];
        int maxsqlen = 0, prev = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = Math.min(Math.min(dp[j - 1], prev), dp[j]) + 1;
                    maxsqlen = Math.max(maxsqlen, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        return maxsqlen * maxsqlen;
    }
}

Sept. 28, 2017, Thursday

 BLANK

1. Array
2. DP
3. String
4. Sort

1. Array

135. Candy

Naive Method

时间复杂度O(n^2) 空间复杂度O(n^2)
一遍一遍的扫,指导所有的位置都满足要求。非常没有效率的方式,但是应该考虑这种类似DFS,有终止条件的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        boolean flag = true;
        int sum = 0;
        while (flag) {
            flag = false;
            for (int i = 0; i < ratings.length; i++) {
                if (i != ratings.length - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                    candies[i] = candies[i + 1] + 1;
                    flag = true;
                }
                if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
                    candies[i] = candies[i - 1] + 1;
                    flag = true;
                }
            }
        }
        for (int candy : candies) {
            sum += candy;
        }
        return sum;
    }
}

Two Array

经典的双向扫描,然后取最大值。
这里,由于对于位置i,左右两边相互独立,这种方式才可以proof。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int candy(int[] ratings) {
        int sum = 0;
        int[] left2right = new int[ratings.length];
        int[] right2left = new int[ratings.length];
        Arrays.fill(left2right, 1);
        Arrays.fill(right2left, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left2right[i] = left2right[i - 1] + 1;
            }
        }
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right2left[i] = right2left[i + 1] + 1;
            }
        }
        for (int i = 0; i < ratings.length; i++) {
            sum += Math.max(left2right[i], right2left[i]);
        }
        return sum;
    }
}

Two Array:Revise

改进了存储,只用一个array,和方法2是同样的原理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        int sum = candies[ratings.length - 1];
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
            sum += candies[i];
        }
        return sum;
    }
}

Single Path

非常经典并且高效的做法。O(1)的空间复杂度,O(n)的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    public int count(int n) {
        return (n * (n + 1)) / 2;
    }
    public int candy(int[] ratings) {
        if (ratings.length <= 1) {
            return ratings.length;
        }
        int candies = 0;
        int up = 0;
        int down = 0;
        int old_slope = 0;
        for (int i = 1; i < ratings.length; i++) {
            int new_slope = (ratings[i] > ratings[i - 1]) ? 1 : (ratings[i] < ratings[i - 1] ? -1 : 0);
            if ((old_slope > 0 && new_slope == 0) || (old_slope < 0 && new_slope >= 0)) {
                candies += count(up) + count(down) + Math.max(up, down);
                up = 0;
                down = 0;
            }//到mountain结束的时候计算,包括终点不包括起点
             //或者到达平台期,下降平台, First value is 1 one and last one decrese again
             //上升平台,first value increase and the other restart form 1
            if (new_slope > 0)
                up++;
            if (new_slope < 0)
                down++;
            if (new_slope == 0)
                candies++;
 
            old_slope = new_slope;
        }
        candies += count(up) + count(down) + Math.max(up, down) + 1;
        return candies;
    }
}

2. DP

132. Palindrome Partitioning II

巧妙地DP

需要考虑到的是,问题和子问题的关系如何设计才满足DP
[j, i] is pal <- c[j] == c[i] && c[j+1][i-1] is pal j+1 is always next step but i-1 the past step i is outter loop while j is inner loop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minCut(String s) {
        char[] c = s.toCharArray();
        int n = c.length;
        int[] cut = new int[n];
        boolean[][] pal = new boolean[n][n];
 
        for(int i = 0; i < n; i++) {
            int min = i;
            for(int j = 0; j <= i; j++) {
                if(c[j] == c[i] && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
                    pal[j][i] = true;  // The table's index is different 
                    min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1);
                    // 0 ... j-1 -> j ... i
                }
            }
            cut[i] = min;
        }
        return cut[n - 1];
    }
}

3. String

214. Shortest Palindrome

Naive Method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public String shortestPalindrome(String s) {
        int len = s.length();
        char[] a = s.toCharArray();
 
        for(int i =len-1; i>=0; i--){
            if(check(a, i)){
                int start = i+1;
                int end = len -1;
                while(start < end){
                    char temp = a[start];
                    a[start] = a[end];
                    a[end] = temp;
                    start ++;
                    end --;
                }
                return new String(a, i+1, len - i-1) + s;
            }
        }
        return "";
    }
 
    public boolean check(char[] a, int end){
        int start = 0;
        while(start < end){
            if(a[start] != a[end]){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

KMP

A very concise video about KMP
There is a KMP trick.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public String shortestPalindrome(String s) {
        String temp = s + "#" + new StringBuilder(s).reverse().toString();
        int[] table = getTable(temp);
 
        return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
    }
 
    public int[] getTable(String s){
        int[] table = new int[s.length()];
 
        int index = 0;
        for(int i = 1; i < s.length(); i++){
            if(s.charAt(index) == s.charAt(i)){
                table[i] = table[i-1] + 1;
                index ++;
            }else{
                index = table[i-1];
                while(index > 0 && s.charAt(index) != s.charAt(i)){
                    index = table[index-1];
                }
                if(s.charAt(index) == s.charAt(i)){
                    index ++ ;
                }
                table[i] = index;
            }
        }
 
        return table;
    }
}

4. Sort

A good demo of redix sort

164. Maximum Gap

Redix Sort

时间复杂度O(dn) d is a constant, parhaps larger than logn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        //Sort Method: General built-in sort: O(nlogn)
        //Radix Sort: O(dn), d = number of digits
        // m is the maximal number in nums
        int m = nums[0];
        for (int i = 1; i < nums.length; i++) {
            m = Math.max(m, nums[i]);
        }
 
        int exp = 1;  
        int R = 10;  
 
        int[] aux = new int[nums.length];
 
        while (m / exp > 0) { // Go through all digits from LSB to MSB
            int[] count = new int[R];
 
            for (int i = 0; i < nums.length; i++) {
                count[(nums[i] / exp) % 10]++;
            }
            // count times 
 
            for (int i = 1; i < count.length; i++) {
                count[i] += count[i - 1];
            }
            // accumulation
 
            for (int i = nums.length - 1; i >= 0; i--) {
                aux[--count[(nums[i] / exp) % 10]] = nums[i];
            }
            // restore
 
            for (int i = 0; i < nums.length; i++) {
                nums[i] = aux[i];
            } //here ius coverage 
 
            // renew the original nums 
            exp *= 10;
        }
 
 
        int max = 0;
        for (int i = 1; i < aux.length; i++) {
            max = Math.max(max, aux[i] - aux[i - 1]);
        }
 
        return max;
    }
}

Bucket Sort

时间复杂度O(n)

The Pigeonhole Principle

n-1个bucket,n-2个元素,则必定有一个bucket为空,所以 max gap > 1 bukcet.length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public int maximumGap(int[] num) {
    if (num == null || num.length < 2)
        return 0;
    // get the max and min value of the array
    int min = num[0];
    int max = num[0];
    for (int i:num) {
        min = Math.min(min, i);
        max = Math.max(max, i);
    }
    // the minimum possibale gap, ceiling of the integer division
    int gap = (int)Math.ceil((double)(max - min)/(num.length - 1));
    int[] bucketsMIN = new int[num.length - 1]; // store the min value in that bucket
    int[] bucketsMAX = new int[num.length - 1]; // store the max value in that bucket
    Arrays.fill(bucketsMIN, Integer.MAX_VALUE);
    Arrays.fill(bucketsMAX, Integer.MIN_VALUE);
    // put numbers into buckets
    for (int i:num) {
        if (i == min || i == max)
            continue;
        int idx = (i - min) / gap; // index of the right position in the buckets
        bucketsMIN[idx] = Math.min(i, bucketsMIN[idx]);
        bucketsMAX[idx] = Math.max(i, bucketsMAX[idx]);
    }
    // scan the buckets for the max gap
    int maxGap = Integer.MIN_VALUE;
    int previous = min;
    for (int i = 0; i < num.length - 1; i++) {
        if (bucketsMIN[i] == Integer.MAX_VALUE && bucketsMAX[i] == Integer.MIN_VALUE)
            // empty bucket
            continue;
        // min value minus the previous value is the current gap
        maxGap = Math.max(maxGap, bucketsMIN[i] - previous);
        // update previous bucket value
        previous = bucketsMAX[i];
    }
    maxGap = Math.max(maxGap, max - previous); // updata the final max value gap
    return maxGap;
}

Sept. 27, 2017, Wendesday

 BLANK

1. DP
2. Union Find

1. DP

87. Scramble String

Traditional DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Let M(i, j, l) = whether the substring S1[i, i + l - 1] is a scramble of S2[j, j + l - 1] or not
// closed interval
//Generally O(n^4)
class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length()) {
            return false;
        }
        if (s1.equals(s2)) {      
            return true;
        }
 
        int len = s1.length();
        boolean[][][] M = new boolean[len][len][len + 1]; 
        for (int l = 1; l <= len; l++) {
            for (int i = 0; i + l - 1 < len; i++) {
                for (int j = 0; j + l - 1 < len; j++) {
                    if (l == 1) {
                        M[i][j][l] = s1.charAt(i) == s2.charAt(j);
                    } else {
                        for (int k = 1; k < l; k++) { // K is seperator between l length
                            if (M[i][j][k] && M[i + k][j + k][l - k] || 
                                    M[i][j + l - k][k] && M[i + k][j][l - k]) {
                                M[i][j][l] = true;
                            }
                        }
                    }
                }
            }    
        }
        return M[0][0][len];   
    }
}

BASIC DFS

TLE solution: 需要考虑剪枝
时间复杂度计算:
T(n) = T(n-1) + T(n-2) + …… + T(1) + 4n^2 = 2T(n-1) + 8n^2
化简后 T(N) = a^n , 一般的可以认为a =2

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) return true;
 
        for (int i=1; i<s1.length(); i++) {
            if (isScramble(s1.substring(0,i), s2.substring(0,i)) 
             && isScramble(s1.substring(i), s2.substring(i))) return true;
            if (isScramble(s1.substring(0,i), s2.substring(s2.length()-i)) 
             && isScramble(s1.substring(i), s2.substring(0,s2.length()-i))) return true;
        }
        return false;
    }
}

DFS

判断了剩余字符串字符数量是否相互匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) return true; 
 
        int[] letters = new int[26];
        for (int i=0; i<s1.length(); i++) {
            letters[s1.charAt(i)-'a']++;
            letters[s2.charAt(i)-'a']--;
        }
        for (int i=0; i<26; i++) if (letters[i]!=0) return false;
 
        for (int i=1; i<s1.length(); i++) {
            if (isScramble(s1.substring(0,i), s2.substring(0,i)) 
             && isScramble(s1.substring(i), s2.substring(i))) return true;
            if (isScramble(s1.substring(0,i), s2.substring(s2.length()-i)) 
             && isScramble(s1.substring(i), s2.substring(0,s2.length()-i))) return true;
        }
        return false;
    }
}

2. Union Find

128. Longest Consecutive Sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int longestConsecutive(int[] num) {
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int n : num) {
            if (!map.containsKey(n)) {
                int left = map.getOrDefault(n - 1, 0);
                int right = map.getOrDefault(n + 1, 0);
                // sum: length of the sequence n is in
                int sum = left + right + 1;
                map.put(n, sum);
 
                res = Math.max(res, sum);
 
                // extend the length to the boundary(s) of the sequence
                // will do nothing if n has no neighbors
                map.put(n - left, sum);
                map.put(n + right, sum);
            }else {
                continue;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
public int longestConsecutive(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
 
    Set<Integer> set = new HashSet<Integer>();
 
    for(int num: nums) set.add(num);
    int max = 1;
    for(int num: nums) {
        if(set.remove(num)) {//num hasn't been visited
            int val = num;
            int sum = 1;
            while(set.remove(val-1)) val--;
            sum += num - val;
 
            val = num;
            while(set.remove(val+1)) val++;
            sum += val - num;
 
            max = Math.max(max, sum);
        }
    }
    return max;
}
}

Sept. 26, 2017, Tuesday

 BLANK

1. Priority Queue
2.

1. Priority Queue

295. Find Median from Data Stream

Small tips: Collections.reverseOrder()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MedianFinder {
    Queue<Integer> minHeap;
    Queue<Integer> maxHeap;
    boolean isOdd;
 
    /** initialize your data structure here. */
    public MedianFinder() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>( Collections.reverseOrder());
        isOdd = false; 
    }
 
    public void addNum(int num) {
        maxHeap.add(num);
        minHeap.add(maxHeap.poll());          
        if (maxHeap.size() < minHeap.size()) {
             maxHeap.add(minHeap.poll());
        }
    }
 
    public double findMedian() {
        return maxHeap.size() > minHeap.size() ? maxHeap.peek() : (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

1. DP

295. Find Median from Data Stream

Traditional DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int numDistinct(String s, String t) {
        int len1 = s.length(), len2 =t.length();
        int[][] table = new int[len1+1][len2+1];
        for(int i=0;i<=len1; i++){
            table[i][0] = 1;
        }
        for(int i =1; i<=len1; i++){
            for(int j =1; j<=len2; j++){
                if(s.charAt(i-1) == t.charAt(j-1)){
                    table[i][j] = table[i-1][j] + table[i-1][j-1];
                }else{
                    table[i][j] = table[i-1][j];
                }
            }
        }
        return table[len1][len2];
    }
}

DFS+Memoization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static int numDistinct(String s, String t) {
        if(s.length()<t.length()) return 0;
        int rs = checkNext(t.toCharArray(),0,
            s.toCharArray(),0,new int[t.length()][s.length()]);
        return rs<0?0:rs;
}
 
private static int checkNext(char[] t,int tarindex,char[] s,int begin,
                                 int[][] memo){
    // flags in the memo: 0 undecided, -1 not match(return directly)
    // other integers represent the numbers of subsequences.
    if(tarindex==t.length) return 1;
    if(memo[tarindex][begin]!=0) return memo[tarindex][begin];
    int count = 0,remain = t.length-tarindex;
    for(int i=begin;i<=s.length-remain;i++){
        if(s[i]==t[tarindex]){
            int rs = checkNext(t,tarindex+1,s,i+1,memo);
            if(rs!=-1) count+=rs;
            else break; // no more subsequences, stop checking
        }
    }
    count = count==0?-1:count;
    memo[tarindex][begin] = count;
    return count;
}

Sept. 25, 2017, Monday

 48. Rotate Image 133. Clone Graph

1. Tree
2. Others

1. Tree

99. Recover Binary Search Tree

In-order traversal

值得注意的是,当树中存在一个交换操作,一定是大的数和小的数交换:
中序遍历,保证了我们先找到被缓过来的的大的树, 而且字底向上的方式,保证了找到的换来的,而不是其周围的,因为保证了找到的数下方都符合规则。
然后,必定找到另一个小的数字。
注意:空间复杂度:平均O(logn) 最坏O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Solution { 
    TreeNode firstElement = null;
    TreeNode secondElement = null;
    // The reason for this initialization is to avoid null pointer exception in the first comparison when prevElement has not been initialized
    TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);
 
    public void recoverTree(TreeNode root) {
 
        // In order traversal to find the two elements
        traverse(root);
 
        // Swap the values of the two nodes
        int temp = firstElement.val;
        firstElement.val = secondElement.val;
        secondElement.val = temp;
    }
 
    private void traverse(TreeNode root) {
 
        if (root == null)
            return;
 
        traverse(root.left);
 
        // Start of "do some business", 
        // If first element has not been found, assign it to prevElement (refer to 6 in the example above)
        if (firstElement == null && prevElement.val >= root.val) {
            firstElement = prevElement;
        }
 
        // If first element is found, assign the second element to the root (refer to 2 in the example above)
        if (firstElement != null && prevElement.val >= root.val) {
            secondElement = root;
        }        
        prevElement = root;
 
        // End of "do some business"
 
        traverse(root.right);
}

Morris traversal

Here is a ggod explanation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode pre = null;
        TreeNode first = null, second = null;
        // Morris Traversal
        TreeNode temp = null;
		while(root!=null){
			if(root.left!=null){
				// connect threading for root
				temp = root.left;
				while(temp.right!=null && temp.right != root)
					temp = temp.right;
				// the threading already exists
				if(temp.right!=null){
				    if(pre!=null && pre.val > root.val){
				        if(first==null){first = pre;second = root;}
				        else{second = root;}
				    }
				    pre = root;
 
					temp.right = null;
					root = root.right;
				}else{
					// construct the threading
					temp.right = root;
					root = root.left;
				}
			}else{
				if(pre!=null && pre.val > root.val){
				    if(first==null){first = pre;second = root;}
				    else{second = root;}
				}
				pre = root;
				root = root.right;
			}
		}
		// swap two node values;
		if(first!= null && second != null){
		    int t = first.val;
		    first.val = second.val;
		    second.val = t;
		}
    }
}

2. Others

329. Longest Increasing Path in a Matrix

DFS + DP –> Memoization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    // brilliant design for check neighbour
 
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] cache = new int[m][n];  //cache the the max increasing length, follow by dfs order
        int max = 1;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int len = dfs(matrix, i, j, m, n, cache);
                max = Math.max(max, len);
            }
        }   
        return max;
    }
 
    public int dfs(int[][] matrix, int i, int j, int m, int n, int[][] cache) {
        if(cache[i][j] != 0) return cache[i][j];
        int max = 1;
        for(int[] dir: dirs) {
            int x = i + dir[0], y = j + dir[1];
            if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue;
            int len = 1 + dfs(matrix, x, y, m, n, cache);
            max = Math.max(max, len);
        }
        cache[i][j] = max;
        return max;
    }
}

560. Subarray Sum Equals K

Map conpute frequency

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int subarraySum(int[] nums, int k) {
        int sum = 0, result = 0;
        Map<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1);
 
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (preSum.containsKey(sum - k)) {
                result += preSum.get(sum - k);
            }
            preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
        }
 
        return result;
    }
}

Sept. 24, 2017, Sunday

 48. Rotate Image 133. Clone Graph

1. UnionFind
2. Others

1. Union Find

684. Redundant Connection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int[] parent = new int[2001];
        for (int i = 0; i < parent.length; i++) parent[i] = i;
 
        for (int[] edge: edges){
            int f = edge[0], t = edge[1];
            if (find(parent, f) == find(parent, t)) return edge; // same root 
            else parent[find(parent, f)] = find(parent, t); // if not, renew root
        }
 
        return new int[2]; // did not find at all
    }
 
    private int find(int[] parent, int f) { // find root node in a graph 
        if (f != parent[f]) { //for root, root's parent must be unchanges, so equals to root's index
          parent[f] = find(parent, parent[f]);  
        }
        return parent[f];
    }
}

2. Others

57. Insert Interval

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new LinkedList<>();
        int i = 0;
 
        //add all before non-overlap intervals 
        while (i < intervals.size() && intervals.get(i).end < newInterval.start)
            result.add(intervals.get(i++));
        // merge all overlap intervals 
        while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
            newInterval = new Interval( 
                    Math.min(newInterval.start, intervals.get(i).start),
                    Math.max(newInterval.end, intervals.get(i).end));
            i++;
        }
        result.add(newInterval);
 
        // add all the rest
        while (i < intervals.size()) result.add(intervals.get(i++)); 
        return result;
    }
}

48. Rotate Image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public void rotate(int[][] matrix) {
        int len = matrix.length;
        for(int i =0;i<len/2; i++){
            for(int j=0;j<len ;j ++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[len -i -1][j];
                matrix[len -i -1][j] = temp;
            }
        }
        for(int i =0;i<len; i++){
            for(int j=i+1;j<len ;j ++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }        
 
    }
}

84. Largest Rectangle in Histogram

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int largestRectangleArea(int[] height) {
        int len = height.length;
        Stack<Integer> s = new Stack<Integer>();
        int maxArea = 0;
        for(int i = 0; i <= len; i++){
            int h = (i == len ? 0 : height[i]);
            if(s.isEmpty() || h >= height[s.peek()]){
                s.push(i);
            }else{
                int tp = s.pop();
                maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
                i--;
            }
        }
        return maxArea;
    }
}

85. Maximal Rectangle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length ==0) return 0;
        int len = matrix.length;
        int wid = matrix[0].length;
        int[] left = new int[wid];
        int[] right = new int[wid];
        Arrays.fill(right, wid);
        int[] height = new int[wid];
        int max =0;
        for(int i =0; i< len ; i++){
            int curLeft = 0;
            int curRight = wid;
            for(int j =0; j< wid; j++){
                if(matrix[i][j] == '1'){
                    height[j] ++;
                }else{
                    height[j] = 0;
                }
            }
 
            for(int j=0; j<wid; j++){
                if(matrix[i][j] == '1'){
                    left[j] = Math.max(left[j], curLeft);
                }else{
                    left[j] = 0;
                    curLeft = j + 1;
                }
            }
 
            for(int j=wid-1; j>=0; j--){
                if(matrix[i][j] == '1'){
                    right[j] = Math.min(right[j], curRight);
                }else{
                    right[j] = wid;
                    curRight = j; // No minus 1 considering the distance computing
                }
            }
 
            for(int j=0; j<wid; j++){
                max= Math.max(max, height[j] *(right[j] -left[j]));
            }                       
        }
        return max;
    }
}

207. Course Schedule

BFS + Topological sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[][] matrix = new int[numCourses][numCourses]; // i -> j
    int[] indegree = new int[numCourses];
 
    for (int i=0; i<prerequisites.length; i++) {
        int ready = prerequisites[i][0];
        int pre = prerequisites[i][1];
        if (matrix[pre][ready] == 0)
            indegree[ready]++; //duplicate case
        matrix[pre][ready] = 1;
    }
 
    int count = 0;
    Queue<Integer> queue = new LinkedList();
    for (int i=0; i<indegree.length; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }// find all root node
 
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int i=0; i<numCourses; i++) {
            if (matrix[course][i] != 0) {
                if (--indegree[i] == 0)
                    queue.offer(i);
            }
        }
    }
    return count == numCourses;
}

DFS + Topological sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            ArrayList[] graph = new ArrayList[numCourses];
            for(int i=0;i<numCourses;i++)
                graph[i] = new ArrayList();
 
            boolean[] visited = new boolean[numCourses];
            for(int i=0; i<prerequisites.length;i++){
                graph[prerequisites[i][1]].add(prerequisites[i][0]);
            }
 
            for(int i=0; i<numCourses; i++){
                if(!dfs(graph,visited,i))
                    return false;
            }
            return true;
        }
 
        private boolean dfs(ArrayList[] graph, boolean[] visited, int course){
            if(visited[course])
                return false;
            else
                visited[course] = true;;
 
            for(int i=0; i<graph[course].size();i++){
                if(!dfs(graph,visited,(int)graph[course].get(i)))
                    return false;
            }
            visited[course] = false;  // backtrack
            return true;
        }
}

97. Interleaving String

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
 
        if ((s1.length()+s2.length())!=s3.length()) return false;
 
        boolean[][] matrix = new boolean[s2.length()+1][s1.length()+1];
 
        matrix[0][0] = true;
 
        for (int i = 1; i < matrix[0].length; i++){
            matrix[0][i] = matrix[0][i-1]&&(s1.charAt(i-1)==s3.charAt(i-1)); 
            //i-1 means i^th char in s1 and s3
            // to match the matrix[][]'s 0 index as placeholder
        }
 
        for (int i = 1; i < matrix.length; i++){
            matrix[i][0] = matrix[i-1][0]&&(s2.charAt(i-1)==s3.charAt(i-1));
        }
 
        for (int i = 1; i < matrix.length; i++){
            for (int j = 1; j < matrix[0].length; j++){
                matrix[i][j] = (matrix[i-1][j]&&(s2.charAt(i-1)==s3.charAt(i+j-1)))
                        || (matrix[i][j-1]&&(s1.charAt(j-1)==s3.charAt(i+j-1)));
            }
        }
 
        return matrix[s2.length()][s1.length()];
 
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isInterleave(String s1, String s2, String s3) {
    char[] c1 = s1.toCharArray(), c2 = s2.toCharArray(), c3 = s3.toCharArray();
	int m = s1.length(), n = s2.length();
	if(m + n != s3.length()) return false;
	return dfs(c1, c2, c3, 0, 0, 0, new boolean[m + 1][n + 1]);
}
 
public boolean dfs(char[] c1, char[] c2, char[] c3, int i, int j, int k, boolean[][] invalid) {
	if(invalid[i][j]) return false;
	if(k == c3.length) return true;
	boolean valid = 
	    i < c1.length && c1[i] == c3[k] && dfs(c1, c2, c3, i + 1, j, k + 1, invalid) || 
        j < c2.length && c2[j] == c3[k] && dfs(c1, c2, c3, i, j + 1, k + 1, invalid);
	if(!valid) invalid[i][j] = true; // Why use invald?
        //for the boolean array default value is false
        // valid make no offence
    return valid;
}

Sept. 23, 2017, Saturday

 Blank

1. Backtrack
2. Others

1. Backtrack

51. N-Queens

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
 
    private void helper(int r, boolean[] cols, boolean[] d1, boolean[] d2, 
                        String[] board, List<String[]> res) {
        if (r == board.length) res.add(board.clone());
        else {
            for (int c = 0; c < board.length; c++) {
                int id1 = r - c + board.length, id2 = 2*board.length - r - c - 1;
                if (!cols[c] && !d1[id1] && !d2[id2]) {
                    char[] row = new char[board.length];
                    Arrays.fill(row, '.'); row[c] = 'Q';
                    board[r] = new String(row);
                    cols[c] = true; d1[id1] = true; d2[id2] = true;
                    helper(r+1, cols, d1, d2, board, res);
                    cols[c] = false; d1[id1] = false; d2[id2] = false;
                }
            }
        }
    }
 
    public List<String[]> solveNQueens(int n) {
        List<String[]> res = new ArrayList<>();
        helper(0, new boolean[n], new boolean[2*n], new boolean[2*n], 
            new String[n], res);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Solution {
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                board[i][j] = '.';
        List<List<String>> res = new ArrayList<List<String>>();
        dfs(board, 0, res);
        return res;
    }
 
    private void dfs(char[][] board, int colIndex, List<List<String>> res) {
        if(colIndex == board.length) {
            res.add(construct(board));
            return;
        }
 
        for(int i = 0; i < board.length; i++) {
            if(validate(board, i, colIndex)) {
                board[i][colIndex] = 'Q';
                dfs(board, colIndex + 1, res);
                board[i][colIndex] = '.';
            }
        }
    }
 
    private boolean validate(char[][] board, int x, int y) {
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < y; j++) {
                if(board[i][j] == 'Q' && (x + j == y + i || x + y == i + j || x == i))
                    return false;
            }
        }
 
        return true;
    }
 
    private List<String> construct(char[][] board) {
        List<String> res = new LinkedList<String>();
        for(int i = 0; i < board.length; i++) {
            String s = new String(board[i]);
            res.add(s);
        }
        return res;
    }
}

52. N-Queens II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    int count = 0;
    public int totalNQueens(int n) {
        boolean[] cols = new boolean[n];     // columns   |
        boolean[] d1 = new boolean[2 * n];   // diagonals \
        boolean[] d2 = new boolean[2 * n];   // diagonals /
        backtracking(0, cols, d1, d2, n);
        return count;
    }
 
    public void backtracking(int row, boolean[] cols, boolean[] d1, boolean []d2, int n) {
        if(row == n) count++;
 
        for(int col = 0; col < n; col++) {
            int id1 = col - row + n;
            int id2 = col + row;
            if(cols[col] || d1[id1] || d2[id2]) continue;
 
            cols[col] = true; d1[id1] = true; d2[id2] = true;
            backtracking(row + 1, cols, d1, d2, n);
            cols[col] = false; d1[id1] = false; d2[id2] = false;
        }
    }
}

2. Others

45. Jump Game II

Greedy

1
2
3
4
5
6
7
8
9
10
11
public int jump(int[] A) {
	int jumps = 0, curEnd = 0, curFarthest = 0;
	for (int i = 0; i < A.length - 1; i++) {
		curFarthest = Math.max(curFarthest, i + A[i]);
		if (i == curEnd) {
			jumps++;
			curEnd = curFarthest;
		}
	}
	return jumps;
}

BFS: Hierarchy Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int jump(int[] nums) {
        int curr_max = 0, next_max = 0, level = 0;
 
        while(next_max<nums.length-1){
            int max = next_max;
            for(int i = curr_max; i<=next_max; i++){
                if(i+nums[i]>max)
                    max = i+nums[i];
            }
            curr_max = next_max+1;
            next_max = max;
            level++;
        }
 
        return level;
    }
}

3. DP

44. Wildcard Matching

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] match=new boolean[s.length()+1][p.length()+1];
        match[s.length()][p.length()]=true;
        for(int i=p.length()-1;i>=0;i--){
            if(p.charAt(i)!='*')
                break;
            else
                match[s.length()][i]=true;
        }
        for(int i=s.length()-1;i>=0;i--){
            for(int j=p.length()-1;j>=0;j--){
                if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?')
                        match[i][j]=match[i+1][j+1];
                else if(p.charAt(j)=='*')
                        match[i][j]=match[i+1][j]||match[i][j+1];
                else
                    match[i][j]=false;
            }
        }
        return match[0][0];
    }
}

Sept. 22, 2017, Fri

Although such a mistake, struggle to fight still!

198. House Robber

1. DP
2. Pointers
3. Stack

1.DP

472. Concatenated Words

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public static List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> result = new ArrayList<>();
        Set<String> preWords = new HashSet<>();
        Arrays.sort(words, new Comparator<String>() {
            public int compare (String s1, String s2) {
                return s1.length() - s2.length();
            }
        });
 
        for (int i = 0; i < words.length; i++) {
            if (canForm(words[i], preWords)) {
                result.add(words[i]);
            }
            preWords.add(words[i]);
        }
 
        return result;
    }
 
    private static boolean canForm(String word, Set<String> dict) {
        if (dict.isEmpty()) return false;
        boolean[] dp = new boolean[word.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= word.length(); i++) {
            for (int j = 0; j < i; j++) {
            if (!dp[j]) continue;
                if (dict.contains(word.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
	        }
	    }
	    return dp[word.length()];
    }
}

2.Pointers

11. Container With Most Water

Proof can be found here

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int start = 0;
        int end = height.length-1;
 
        while(start < end){
            max =Math.max(max, (end-start) * Math.min(height[start], height[end]));
            if(height[end] < height[start]){
                end --;
            }else{
                start ++;
            }
        }
        return max;
 
    }
}

2.Pointers

153. Find Minimum in Rotated Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findMin(int[] nums) {
        int start =0;
        int end = nums.length -1;
 
        //Must compare end and mid for end never equals to mid
        //and eliminate the possible possition of minimus is at index =0 
        while(start < end){
            int mid = start + (end - start)/2;
            if( nums[mid] < nums[end]){
                end = mid;
            }else if( nums[mid] > nums[end]){
                start = mid +1;
            }
        }
        return nums[start]; 
        // or return end is OK
        //for start always equals end after loop
 
    }
}

154. Find Minimum in Rotated Sorted Array II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Worst case: O(n)
 **/
class Solution {
    public int findMin(int[] nums) {
        int start = 0;
        int end = nums.length -1;
        while( start < end){
            int mid = start + (end -start)/2;
            if( nums[end] < nums[mid]){
                start = mid +1;
            }else if(nums[end] > nums[mid]){
                end = mid;
            }else{
                end--;
            }
        }
        return nums[start];
    }
}

3.Stack

150. Evaluate Reverse Polish Notation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int evalRPN(String[] tokens) {
        //int a,b;
        Stack<Integer> stack = new Stack<Integer>();
        for (String s : tokens){
            switch (s){
                case "+": stack.push(stack.pop()+stack.pop());break;
                case "-": stack.push(-stack.pop()+stack.pop());break;
                case "*": stack.push(stack.pop()*stack.pop());break;
                case "/": int a = stack.pop(); int b = stack.pop(); stack.push(b/a);
                break;     
                default: stack.push(Integer.parseInt(s));break;
            }
        }
 
        return stack.pop();
	}
}

Sept. 21, 2017, Thursday

Now is 2:55 pm. About 8 hrs are spent! Work hard!

 Leetcode23 leetcode160(intersection)

1. Math

1. Math

150. Pow(x, n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 *  This is a neat recursive solution; avoid the MIN_VALUE's opposite overflow
 **/
public class Solution {
    public double myPow(double x, int n) {
        if(n == 0) return 1.;
        double res = myPow(x, n / 2);
        if(n%2 == 0){
            return res * res;
        }else{
            if(n < 0){
                return (1/x) * res * res;
            }
            return x * res * res;
        }
    }
}
/**
 *  This is shadow version of last example: just change the condition
 *  Need to  consider if the n % 2 ==0 -1 or 1
 **/
public class Solution {
    double myPow(double x, int n) { 
        if(n==0) return 1;
        double t = myPow(x,n/2);
        if((n & 1) == 1) return n<0 ? 1/x*t*t : x*t*t;
        else return t*t;
    }
}
/**
 *  This is another recursive solution: You had add n = 2 case to eliminate the dead loop
 **/
public class Solution {
    public double myPow(double x, int n) {
        if(n==0) return 1;
        if(n<0) 
            return 1/x * myPow(1/x, -(n+1));
        else{
            if(n==2) return x*x;
            if(n%2==0)
                return myPow( myPow(x, n/2), 2);
            else 
                return x*myPow( myPow(x, n/2), 2);            
        }
    }
}
/**
 *  A deliberate iterative version: avoid the overflow and compensate for the lost one factor x
 **/
    public double myPow(double x, int n) {
        // Write your code here
        boolean isNegative = false;
        if (n < 0) {
            x = 1 / x;
            isNegative = true;
            n = -(n + 1); // Avoid overflow when n == MIN_VALUE
        }
 
        double ans = 1, tmp = x;
 
        while (n != 0) {
            if (n % 2 == 1) {
                ans *= tmp;
            }
            tmp *= tmp;
            n /= 2;
        }
 
        if (isNegative) {
            ans *= x;
        }
        return ans;
    }

2. String

139. Word Break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> dict = new HashSet<>(wordDict);
        boolean[] dp = new boolean[n + 1]; //represents if the string s can be split by dict
        dp[0] = true;
 
        for(int i = 0; i < n; i++) {
            if(dp[i]) {
                for(int j = i + 1; j <= n; j++) {
                    if(dict.contains(s.substring(i, j)) ) {
                        dp[j] = true;
                    }
                }
            }
        }
        return dp[n];
    }
}

140. Word Break II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<String>(wordDict);
        return DFS(s, set, new HashMap<String, LinkedList<String>>());
    }       
 
    // DFS function returns an array including all substrings derived from s.
    List<String> DFS(String s, Set<String> wordDict, HashMap<String, LinkedList<String>>map) {
        if (map.containsKey(s)) 
            return map.get(s);
 
        LinkedList<String>res = new LinkedList<String>();     
        if (s.length() == 0) {
            res.add("");
            return res;
        }               
        for (String word : wordDict) {
            if (s.startsWith(word)) {
                List<String>sublist = DFS(s.substring(word.length()), wordDict, map);
                for (String sub : sublist) 
                    res.add(word + (sub.isEmpty() ? "" : " ") + sub);               
            }
        }       
        map.put(s, res);
        return res;
    }
}