At first, I use the idea of Permutations to get all combinations, and then to detect whether they are palindrome.
The code is show below:
public class Solution {
public List<String> generatePalindromes(String s) {
List<String> result = new LinkedList<>();
if (s == null || s.length() == 0 ) return result;
List<Character> dict = new ArrayList<>();
HashSet<String> duplicates = new HashSet<>();
for(int i = 0; i < s.length(); i++){
dict.add(s.charAt(i));
}
StringBuilder sb = new StringBuilder();
helper(s,dict,sb,result,duplicates);
return result;
}
private void helper(String s, List<Character> dict, StringBuilder sb, List<String> result,HashSet<String> duplicates) {
if (sb.length() == s.length()){
String candidate = sb.toString();
if (isPalindrome(candidate) && !duplicates.contains(candidate))
result.add(candidate);
duplicates.add(candidate);
} else {
for (int i = 0; i < dict.size(); i++) {
char c = dict.get(i);
sb.append(c);
dict.remove(i);
helper(s,dict,sb,result,duplicates);
dict.add(c);
sb.deleteCharAt(sb.length()-1);
}
}
}
public boolean isPalindrome(String s) {
int begin = 0, end = s.length()-1;
while (begin < end) {
if (s.charAt(begin) !=s.charAt(end)){
return false;
} else {
begin++;
end--;
}
}
return true;
}
}
-------------------------------------------------------------------------------------------------------------------------------------
However, this method is TLE.
As I read the hint, I find out the reason. We only need to generate half of the string, the other half can be produced from the first part.
Remember they are palindrome :)
So, I modified the code:
Saturday, December 5, 2015
Sunday, November 29, 2015
Burst Balloons
Be Naive First
When I first get this problem, it is far from dynamic programming to me. I started with the most naive idea the backtracking.
We have n balloons to burst, which mean we have n steps in the game. In the i th step we have n-i balloons to burst, i = 0~n-1. Therefore we are looking at an algorithm of O(n!). Well, it is slow, probably works for n < 12 only.
Of course this is not the point to implement it. We need to identify the redundant works we did in it and try to optimize.
Well, we can find that for any balloons left the maxCoins does not depends on the balloons already bursted. This indicate that we can use memorization (top down) or dynamic programming (bottom up) for all the cases from small numbers of balloon until n balloons. How many cases are there? For k balloons there are C(n, k) cases and for each case it need to scan the k balloons to compare. The sum is quite big still. It is better than O(n!) but worse than O(2^n).
Better idea
We than think can we apply the divide and conquer technique? After all there seems to be many self similar sub problems from the previous analysis.
Well, the nature way to divide the problem is burst one balloon and separate the balloons into 2 sub sections one on the left and one one the right. However, in this problem the left and right become adjacent and have effects on the maxCoins in the future.
Then another interesting idea come up. Which is quite often seen dp problem analysis. That is reverse thinking. Like I said the coins you get for a ballon does not depend on the balloons already burst. Therefore instead of divide the problem by the first balloon to burst, we divide the problem by the last balloon to burst.
Why is that? Because only the first and last balloons we are sure of their adjacent balloons before hand!
For the first we have
nums[i-1]*nums[i]*nums[i+1] for the last we have nums[-1]*nums[i]*nums[n].
OK. Think about n balloons if i is the last one to burst, what now?
We can see that the balloons is again separated into 2 sections. But this time since the balloon i is the last balloon of all to burst, the left and right section now has well defined boundary and do not effect each other! Therefore we can do either recursive method with memoization or dp.
Final
Here comes the final solutions. Note that we put 2 balloons with 1 as boundaries and also burst all the zero balloons in the first round since they won't give any coins. The algorithm runs in O(n^3) which can be easily seen from the 3 loops in dp solution.
Java D&C with Memoization
public int maxCoins(int[] iNums) {
int[] nums = new int[iNums.length + 2];
int n = 1;
for (int x : iNums) if (x > 0) nums[n++] = x;
nums[0] = nums[n++] = 1;
int[][] memo = new int[n][n];
return burst(memo, nums, 0, n - 1);
}
public int burst(int[][] memo, int[] nums, int left, int right) {
if (left + 1 == right) return 0;
if (memo[left][right] > 0) return memo[left][right];
int ans = 0;
for (int i = left + 1; i < right; ++i)
ans = Math.max(ans, nums[left] * nums[i] * nums[right]
+ burst(memo, nums, left, i) + burst(memo, nums, i, right));
memo[left][right] = ans;
return ans;
}
Java DP
public int maxCoins(int[] iNums) {
int[] nums = new int[iNums.length + 2];
int n = 1;
for (int x : iNums) if (x > 0) nums[n++] = x;
nums[0] = nums[n++] = 1;
int[][] dp = new int[n][n];
for (int k = 2; k < n; ++k)
for (int left = 0; left < n - k; ++left) {
int right = left + k;
for (int i = left + 1; i < right; ++i)
dp[left][right] = Math.max(dp[left][right],
nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
}
return dp[0][n - 1];
}Tuesday, November 17, 2015
2Sum in BST
Zenefits: 2Sum in BST
Input: A binary search tree, consisting of integers. And a number k
Output: True if there are two nodes a and b in the tree, such that a.val + b.val = k.
Return false otherwise.
A O(n) time, O(n) space solution:
The most straight-forward solution is first do a in-order traverse of the BST, store the results into an array. Then the problem can be transformed into a 2 sum problem.
So the time and space complexity for this solution is O(n).
A O(n) time, O(log n) space solution:
Output: True if there are two nodes a and b in the tree, such that a.val + b.val = k.
Return false otherwise.
A O(n) time, O(n) space solution:
The most straight-forward solution is first do a in-order traverse of the BST, store the results into an array. Then the problem can be transformed into a 2 sum problem.
So the time and space complexity for this solution is O(n).
A O(n) time, O(log n) space solution:
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| import java.util.*;public class Solution { public boolean twoSumBST(TreeNode root, int k) { if (root == null) { return false; } Stack<TreeNode> leftStack = new Stack<>(); Stack<TreeNode> rightStack = new Stack<>(); TreeNode p = root; while (p != null) { leftStack.push(p); p = p.left; } p = root; while (p != null) { rightStack.push(p); p = p.right; } p = leftStack.peek(); TreeNode q = rightStack.peek(); while (p.val < q.val && p != q) { if (p.val + q.val == k) { return true; } else if (p.val + q.val < k) { leftStack.pop(); if (p.right != null) { p = p.right; while (p != null) { leftStack.push(p); p = p.left; } } if (leftStack.isEmpty()) { return false; } p = leftStack.peek(); } else if (p.val + q.val > k) { rightStack.pop(); if (q.left != null) { q = q.left; while (q != null) { rightStack.push(q); q = q.right; } } if (rightStack.isEmpty()) { return false; } q = rightStack.peek(); } } return false; } public static void main(String[] args) { Solution solution = new Solution(); TreeNode root = new TreeNode(4); root.left = new TreeNode(2); root.right = new TreeNode(6); root.left.left = new TreeNode(1); root.left.right = new TreeNode(3); root.right.left = new TreeNode(5); root.right.right = new TreeNode(8); boolean result = solution.twoSumBST(root, 3); System.out.println(result); }}class TreeNode { int val; TreeNode left, right; public TreeNode(int val) { this.val = val; left = null; right = null; }} |
Subscribe to:
Posts (Atom)