Daily LeetCode #10
This is a backtrace problem. We check all possbile combinations, and find out the one with most unique substrings.
Steps:
- create a HashMap to store already used substrings
- in the
backtrack
funtion, we select one substring, check if it is the HashMap - if already exists, skip this subtstring; else put it into HashMap
- do
backtrack
recursively withcount + 1
, since we just select one substring - whenenver we reach the tree leave, update
max
- after finishing checking this subtree, remove the substring and move to the next tree
For example, for s = "aba"
:
- select
a
, put it into HashMap, do backtrack onba
; selectb
, put it into HashMap; selecta
, already exists, skip; reach tree node, currentmax
is2
, updatemax
to2
; removeb
, selectba
, put it into HashMap; reach tree node, currentmax
is2
, no update - remove
a
, selectab
, put it into HashMap, do backtrack ona
; selecta
, put it into HashMap; reach tree leave, currentmax
is2
, no update - remove
ab
, selectaba
, put it into HashMap; reach tree leave, currentmax
is1
, no update
class Solution {
HashMap <String, Integer> hash = new HashMap<>();
int max = 0;
public int maxUniqueSplit(String s) {
backtrack(s, 0, 0);
return max;
}
public void backtrack(String s, int start, int count) {
// reach tree leave
if (start == s.length()) {
max = Math.max(max, count);
return;
}
for(int end = start + 1; end <= s.length(); end++) {
String curr = s.substring(start, end);
// discard
if(hash.containsKey(curr)) {
continue;
}
// do selection
hash.put(curr, 0);
backtrack(s, end, count+1);
// rollback
hash.remove(curr);
}
}
}
Note:
Since only use HashMap
to store existing substrings
, the second parameter Integer
does not matter.
Time Complexity: O(n 2n)
[We need to check all possible 2n combinations, for each combination we use substring
, which is O(n)
]
Space Complexity: O(n)
Use BFS to traverse the tree layer by layer.
Steps:
- initialize
Queue
to startBFS
, and a list to store layer sum - add
root
intoqueue
- iterate
n
time,n
is the current size ofqueue
- after adding node vals, add current node's children into
queue
- after each layer, add the layer value sum into the list
- sort the list to get
kth
largest layer sum
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public long kthLargestLevelSum(TreeNode root, int k) {
Queue<TreeNode> q = new LinkedList<>();
List<Long> list = new ArrayList<>();
// BFS
q.add(root);
while(!q.isEmpty()) {
int size = q.size();
long sum = 0;
for(int i = 0; i < size; i++) {
TreeNode curr = q.poll();
sum += curr.val;
if(curr.left != null) q.add(curr.left);
if(curr.right != null) q.add(curr.right);
}
// one layer finishes after each for loop
list.add(sum);
}
if(k > list.size()) return -1;
// sort
Collections.sort(list, Collections.reverseOrder());
return list.get(k - 1);
}
}
Notes:
Collections.sort(list, Collections.reverseOrder())
sort is from Collections
, use reverseOrder()
to sort in descending
order
Time Complexity: O(nlog(n))
[BFS
is O(n)
; sort is O(nlog(n))
in the worst case that the tree has n
layer]
Space Complexity: O(n)
The basic idea is to do BFS
twice.
The first BFS
is to caculate sum for each layer, and record sibling node for each node.
The second BFS
is to update the node val.
Steps:
- the first
BFS
is almost the same to the last question - in addition to that, use a
HashMap
to store<TreeNode, its sibling node's val>
to help later calculation - the second
BFS
has a integerlayer
to indicate current layer - check if current node is top three node, update their
val
to0
; otherwise, caculate bylayerSum - self's val - sibling's val
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode replaceValueInTree(TreeNode root) {
// queue for BFS
Queue<TreeNode> q = new LinkedList<>();
// store sum of each level
List<Integer> levelSum = new ArrayList<>();
// store sibling nodes: (node, its sibling node's value)
HashMap<TreeNode, Integer> hash = new HashMap<>();
// first time BFS: get levelSum and Sibling info
q.add(root);
while(!q.isEmpty()) {
int size = q.size();
int currSum = 0;
for(int i = 0; i < size; i++) {
TreeNode curr = q.poll();
currSum += curr.val;
// add sibling value to hash
if(curr.left != null) {
q.add(curr.left);
hash.put(curr.left, (curr.right != null) ? curr.right.val : 0);
}
if(curr.right != null) {
q.add(curr.right);
hash.put(curr.right, (curr.left != null) ? curr.left.val : 0);
}
}
levelSum.add(currSum);
}
// second BFS: update node value
q.add(root);
int level = 0;
while(!q.isEmpty()) {
int size = q.size();
for(int i = 0; i < size; i++) {
TreeNode curr = q.poll();
// top three nodes
if(curr == root || curr == root.left || curr == root.right) {
curr.val = 0;
} else {
// other nodes
curr.val = levelSum.get(level) - curr.val - hash.get(curr);
}
if(curr.left != null) q.add(curr.left);
if(curr.right != null) q.add(curr.right);
}
level++;
}
return root;
}
}
Time Complexity: O(n)
[BFS
is O(n)
; HashMap
operation is O(1)
]
Space Complexity: O(n)