Expression Add Operators

https://leetcode.com/problems/expression-add-operators/

Looked at this awesome post: https://discuss.leetcode.com/topic/24523/java-standard-backtrace-ac-solutoin-short-and-clear

Recursion, recursion, recursion. It’s the beauty of computer science. It’s so powerful and could be applied to solve so many problems!

public List<String> addOperators(String num, int target) {
List<String> res = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
dfs(res, sb, num, 0, target, 0, 0);
return res;

}

private void dfs(List<String> res, StringBuilder sb, String num, int pos, int target, long prev, long multi) {
if(pos == num.length()){
if(target == prev) res.add(sb.toString());
return;
}
for(int i = pos; i < num.length(); i++){
if(num.charAt(pos) == '0' && i != pos) break;
long curr = Long.parseLong(num.substring(pos, i+1));
int len = sb.length();
if(pos == 0){
dfs(res, sb.append(curr), num, i+1, target, curr, curr);
sb.setLength(len);
} else {
dfs(res, sb.append("+").append(curr), num, i+1, target, prev+curr, curr);
sb.setLength(len);

dfs(res, sb.append("-").append(curr), num, i+1, target, prev-curr, -curr);
sb.setLength(len);

dfs(res, sb.append("*").append(curr), num, i+1, target, prev - multi + multi*curr, multi*curr);
sb.setLength(len);
}
}
}

Advertisements

Data Stream as Disjoint Intervals

https://leetcode.com/problems/data-stream-as-disjoint-intervals/

  • I’m thinking to maintain the numbers as a sorted array, but it doesn’t give me quick insertion into the correct place
  • Then I was thinking to use the previous problem Insert Interval to help with this one, but that’s purely cheating and I’m not if that can work either.
  • The moment, I clicked the Tag, it shows Binary Search Tree, I’m impressed!
    • It’s this thought process that values! Don’t click to show Tags too early, think about it, which data structure would you come up to use?
  • Now, my thoughts:
    • try to use the idea from https://fishercoder.com/2016/07/16/count-of-smaller-numbers-after-self/
    • to build a BST, while inserting a new node, check to see if merge is needed, check both the node’s parent and child, let each node’s value be the lower boundary of the interval and define another field which is the array of interval in this node class
    • after trial and error, rewriting it multiple times: discussion with badyu2000@ here: https://discuss.leetcode.com/topic/47084/java-fast-log-n-solution-186ms-without-using-the-treemap-but-a-customized-bst/12
    • I’ve got my 100% original code to pass 8/9 test cases, I’m really excited about it, my thought process could be visited in that thread, but I’m still puzzled why the last case didn’t pass, from my eyes check, I don’t see any difference between my output and the expected output.

Word Break II

https://leetcode.com/problems/word-break-ii/

Approach 1: https://discuss.leetcode.com/topic/27855/my-concise-java-solution-based-on-memorized-dfs

It iterates the wordDict, pretty concise code, clever memoized DFS, but doesn’t really scale well the given wordDict is huge while the given String s is small.


public List<String> wordBreak(String s, Set<String> wordDict) {
return dfs(s, wordDict, new HashMap<String, ArrayList<String>>());
}

private List<String> dfs(String s, Set<String> wordDict,
HashMap<String, ArrayList<String>> map) {
if(map.containsKey(s)){
return map.get(s);
}

ArrayList<String> res = new ArrayList<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.length() == 0 ? "" : " ") + sub);
}
}
}
map.put(s, res);
return res;
}

 

Approach 2: https://discuss.leetcode.com/topic/8178/slightly-modified-dp-java-solution

This is closer to my own original idea, but I didn’t sort it out and implement the code, whenever there’s a repeated pattern, it’s a good candidate for recursion and dp, I should sit down more calmly and figure out the pattern.

boolean containsSuffix(String str, Set<String> wordDict){
for(int i = 0; i < str.length(); i++){
if(wordDict.contains(str.substring(i))) return true;
}
return false;
}

Map<String, List<String>> cache = new HashMap<>();

public List<String> wordBreak(String s, Set<String> wordDict) {
if(cache.containsKey(s)) return cache.get(s);

List<String> res = new ArrayList<String>();
if(wordDict.contains(s)) res.add(s);

for(int i = 1; i < s.length(); i++){
String left = s.substring(0, i), right = s.substring(i);
if(wordDict.contains(left) && containsSuffix(right, wordDict)){
for(String sub : wordBreak(right, wordDict)){
res.add(left + (sub.length() == 0 ? "" : " ") + sub);
}
}
}
cache.put(s, res);
return res;
}

Combination Sum II

https://leetcode.com/problems/combination-sum-ii/

After completely understanding the previous post, this one becomes a piece of cake, all I did was to change to recursive call inside the function from  to i+1, this way, it will not add the same number when trying to find one potential combination. Also, I used a set to filter out duplicate combinations (the reason for duplicate combinations to occur is because there might be duplicate numbers in the given array, which resulted in the same combination). Also, sorting the array in the first place matters, because we will exit the for loop once we find target is greater than candidates[i], if it’s not sorted, we’ll miss checking the rest of the numbers.


public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
//sort the candidates
Arrays.sort(candidates);

getResult(result, new LinkedList<Integer>(), candidates, target, 0);
return result;
}

void getResult(List<List<Integer>> res, LinkedList<Integer> curr, int[] candidates, int target, int start){
if(target > 0){
for(int i = start; i < candidates.length && target >= candidates[i]; i++){
curr.add(candidates[i]);
getResult(res, curr, candidates, target - candidates[i], i);
curr.remove(curr.size()-1);
}
} else if(target == 0){
res.add(new ArrayList<Integer>(curr));
}
}

public static void main(String...strings){
CombinationSum_20160718 test = new CombinationSum_20160718();
int[] candidates = new int[]{2,3,6,7};
int target = 7;
test.combinationSum(candidates, target);
}

Combination Sum

https://leetcode.com/problems/combination-sum/

I’m really impressed by this solution: https://discuss.leetcode.com/topic/7698/java-solution-using-recursive

I need to understand/grasp recursion more deeply to learn to apply it to solve different problems. Like this one, I should be able to solve it as proficiently as solving those DFS tree problems.

Notes:

  • In the recursive call, there are two base cases:
    1. when the target equals zero, that means, the current path curr is a valid combination, thus we’ll add it into the result
    2. the other base case is implicit, when the target is smaller than zero, it just returns, thus it also went back to after the recursive call, to this line: curr.remove(curr.size()-1); and then adds the next candidate number into curr and continue the recursion
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
//sort the candidates
Arrays.sort(candidates);

getResult(result, new LinkedList<Integer>(), candidates, target, 0);
return result;
}

void getResult(List<List<Integer>> res, LinkedList<Integer> curr, int[] candidates, int target, int start){
if(target > 0){
for(int i = start; i < candidates.length && target >= candidates[i]; i++){
curr.add(candidates[i]);
getResult(res, curr, candidates, target - candidates[i], i);
curr.remove(curr.size()-1);
}
} else if(target == 0){
res.add(new ArrayList<Integer>(curr));
}
}