Posts

HashSet I

Image
HashSet is faster and more memory efficient than HashTable. If you don't need the actual hash value, only the hash set, prefer to use HashSet over HashTable. The solution to the problem below exemplifies this situation. I didn't test with HashTable, but I'm sure it would be slower. Cheers, ACC. Partition String - LeetCode Given a string  s , partition it into  unique segments  according to the following procedure: Start building a segment beginning at index 0. Continue extending the current segment character by character until the current segment has not been seen before. Once the segment is unique, add it to your list of segments, mark it as seen, and begin a new segment from the next index. Repeat until you reach the end of  s . Return an array of strings  segments , where  segments[i]  is the  i th  segment created.   Example 1: Input:   s = "abbccccd" Output:   ["a","b","bc","c","cc","d"] Explanation:...

A non-recursive trick for subsets generation II

Image
This problem requires finding out all the subsets of a small set S. For each subset S', you need to determine whether: Product(S') == Product(S - S') == Target Hence you need to find all S'. Subsets generation trick, as explained before on post I with the same title, does the trick here for an exponential-time solution, but since |S| is small (12), it works just fine. Bonus points for early termination whenever we reach a dead end. Code is down below, cheers, ACC. Partition Array into Two Equal Product Subsets - LeetCode You are given an integer array  nums  containing  distinct  positive integers and an integer  target . Determine if you can partition  nums  into two  non-empty   disjoint   subsets , with each element belonging to  exactly one  subset, such that the product of the elements in each subset is equal to  target . Return  true  if such a partition exists and  false  otherwise. A  subse...