140 LeetCode Java: Word Break II – Hard

Problem:
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

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”].
Thoughts:
A easily modified version from Word Break I shown below is having Time Limit Exceeded issue when you submit.
Probably this is because string manipulation is taking more time comparing just only keep a record of index.

Solutions:

public class Solution {
    private void search(int index, String s, List<Integer> path,
                   boolean[][] isWord, boolean[] possible,
                   List<String> result) {
        if (!possible[index]) {
            return;
        }
        
        if (index == s.length()) {
            StringBuilder sb = new StringBuilder();
            int lastIndex = 0;
            for (int i = 0; i < path.size(); i++) {
                sb.append(s.substring(lastIndex, path.get(i)));
                if (i != path.size() - 1) sb.append(" ");
                lastIndex = path.get(i);
            }
            result.add(sb.toString());
            return;
        }
        
        for (int i = index; i < s.length(); i++) {
            if (!isWord[index][i]) {
                continue;
            }
            path.add(i + 1);
            search(i + 1, s, path, isWord, possible, result);
            path.remove(path.size() - 1);
        }
    }
    
    public List<String> wordBreak(String s, Set<String> wordDict) {
        ArrayList<String> result = new ArrayList<String>();
        if (s.length() == 0) {
            return result;
        }
        
        boolean[][] isWord = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String word = s.substring(i, j + 1);
                isWord[i][j] = wordDict.contains(word);
            }
        }
        
        boolean[] possible = new boolean[s.length() + 1];
        possible[s.length()] = true;
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (isWord[i][j] && possible[j + 1]) {
                    possible[i] = true;
                    break;
                }
            }
        }
        
        List<Integer> path = new ArrayList<Integer>();
        search(0, s, path, isWord, possible, result);
        return result;
    }
}

132 LeetCode Java: Palindrome Partitioning II – Hard

Problem:
Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = “aab”,
Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.
Thoughts:
This is very similar with the first version of the problem. Palindrome Partitioning. The difference is that instead of generating all the partition, we need the minimum cut now.
It’s fine to still generate all the partition and then count the cut of each partition.
But there could be better way to solve this in DP.
We still needs a helper matrix isP[i][j] to indicate if substring i…j (including) is a palindrome.
Then another one dimension array is min[i] indicate the minimum cut for substring 0…i (including).

min[i] = 0 when i = 1
min[i] = 0 when i > 1 and 0…i is a palindrome
min[i] = minimum of min[j] + 1 where j is 1..i(including) when i > 1 and 0…i is not a palindrome

Solutions:

public class Solution {
    public int minCut(String s) {
        if (s == null || s.length() <= 1) {
            return 0;
        }
        boolean[][] isP = new boolean[s.length()][s.length()];
        calIsP(isP, s);
        int[] min = new int[s.length()];
        min[0] = 0;
        for (int i = 1; i < s.length(); i ++) {
            if (isP[0][i] == true) {
                min[i] = 0;
                continue;
            }
            int minC = Integer.MAX_VALUE;
            for (int j = 1; j <=i; j ++) {
                if (isP[j][i] == true) {
                    minC = Math.min(minC, min[j-1] + 1);
                }    
            }
            min[i] = minC;
        }
        return min[s.length() -1];
    }
    private void calIsP(boolean[][] isP, String s) {
        for (int i = 0; i < s.length(); i ++) {
            isP[i][i] = true;
        }
        for (int i = 0; i < s.length() - 1; i ++) {
            isP[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }
        for (int k = 2; k < s.length(); k ++) {
            for (int i = 0; i + k < s.length(); i ++) {
                isP[i][i + k] = s.charAt(i) == s.charAt(i + k) && isP[i + 1][i + k - 1] == true;
            }
        }
    }
}

123 LeetCode Java: Best Time to Buy and Sell Stock III – Hard

Problem:
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Thoughts:
We will need to divide this problem into two subproblem. We find the max profit for range 0..i and i + 1..n -1, then we add up the two max profit we will get the expected result.
Solutions:

public class Solution {
    public int maxProfit(int[] prices) {
        int[] first = new int[prices.length];
        //first[i] is the max profit for the range 0 .. i, 
        int minPrice = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0; i < prices.length; i ++) {
            minPrice = Math.min(minPrice, prices[i]);
            max = Math.max(max, prices[i] - minPrice);
            first[i] =  max;
        }
        int maxPrice = Integer.MIN_VALUE;
        max = 0;
        for (int i = prices.length - 1; i > 0; i --) {
            maxPrice = Math.max(maxPrice, prices[i]);
            max = Math.max(max, maxPrice - prices[i] + first[i-1]);
        }
        if (prices.length > 0) {
            max = Math.max(max, first[first.length - 1]);
        }
        return max;
    }
}

88 LeetCode Java: Merge Sorted Array

Problem:
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

Thoughts:
This is a quite straightforward problem. Only one trick is that we need to merge two sorted array from the right to left not the other way around.
Because we need to merge two array in place and cannot overwrite unmerged element.

Solution:
This version the code is more clear, only one loop.

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        m --;
        n --;
        for (int i = m + n + 1; i >=0; i --) {
            int a = m >=0 ? nums1[m]:Integer.MIN_VALUE;
            int b = n >=0 ? nums2[n]:Integer.MIN_VALUE;
            if (a > b) {
                nums1[i] = a;
                m --;
            }
            else {
                nums1[i] = b;
                n --;
            }
        }
    }
}

Here is an alternative solution.

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        m --;
        n --;
        int i = m + n + 1;
        while (m >=0 && n >=0) {
            if (nums1[m] > nums2[n]) {
                nums1[i--] = nums1[m--];
            }
            else {
                nums1[i--] = nums2[n--];
            }
        }
        while (m >=0) {
            nums1[i--] = nums1[m--];
        }
        while (n >=0) {
            nums1[i--] = nums2[n--];
        }
    }
}

81. Leetcode Java Search in Rotated Sorted Array II

Problem:
Version I:
Suppose a sorted array 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.

Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Thoughts:
In version I we use condition to check if left half or right half is sorted. This depends on element doesn’t have duplicate.
When it allows duplicates, e.g
[1, 3, 1, 1, 1],
nums[start] <= nums[mid] is not good enough to say left half is sorted.
We can only use nums[start] < nums[mid] to say left half is sorted.
Then what about nums[start] = nums[mid]?
When that happens, we can only say the target is not in nums[start], and that' all we can know so far. So we just increase start index in this case.

With that being said, the worst case would be end up with O(n). which means you have to check every single element in the array.

Solution:

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

33 LeetCode Java: Search in Rotated Sorted Array – Hard

Problem:
Suppose a sorted array 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.

Thoughts
If the sorted array is not rotated, then this is a question of standard binary search. However, when the array is rotated, we will need some modification of standard binary search.

Modify the checking condition when moving start and end pivot in standard binary search. We get the mid element of given start and end. If the element equals the target, then good, we can return the index.

img_8892

After we calculate the mid index, let’s see where the mid is at. In the picture above, there are two cases for the mid point. Either at A or at B.
When mid is at A, we need to find a way to determine if we want to go to the left half or right half. We can see that the easier way is to check the left half, which is nums[start] <=target < nums[mid]. Otherwise, it’s falling into the right half.
Similar strategy applies for the case when mid is at point B.

Solutions:

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

How to use diff command in Linux? How to compare two files difference?

diff is a very useful command when you want to compare two files.

basic use of diff is:

diff fileA fileB

Say if fileA is:

Both are convinced
that a sudden surge of emotion bound them together.
Beautiful is such a certainty,
but uncertainty is more beautiful.

Because they didn’t know each other earlier, they suppose that
nothing was happening between them.
What of the streets, stairways and corridors

fileB is:

Both of us are convinced
that a sudden surge of emotion bound them together.
but uncertainty is more beautiful.

Because they didn’t know each other earlier, they suppose that
nothing was happening between them.
What of the streets, stairways and corridors
where they could have passed each other long ago?

The output of diff fileA fileB would be:

1c1

< Both are convinced

> Both of us are convinced

3d2

< Beautiful is such a certainty,

8a8

> where they could have passed each other long ago?

\ No newline at end of file

Let’s read the output.

If two files are identical output would be empty, otherwise it would be an instruction for modifying fileA to become fileB.

1c1 means change line 1 in fileA to match line 1 in fileB.

3d2 means delete line 3 in fileA to match line 2 in fileB.

8a8 means add a new line in line 8 in fileA to match line 8 in fileB.

So the first number is the line numbers in fileA, letter means action, c for change, d for delete, a for add and last number is for line numbers in fileB.

Line numbers could be multiple as well, like 2,5 means line 2 to line 5.

For more advanced comparison, checkout the manuals by running command

man diff