Python

Challenge Given a String S return all palindrome partitions. Example 1: Input: s = "abc" Output: [["a","b","c"] Example 2: Input: s = "abb" Output: [["a","bb"],["a", "b", "b"]] Solution Get all subset of the string. Check if this subset is only composed of palindromes If so add it to the result class Solution: def check_palindrome(self, s): stack = [] for e in list(s): stack.insert(0, e) for e in s: i = stack.pop(0) if i != e: return False return True def get_all_subsets(self, start, s, arr): if arr and not 0 in arr: self._set.add(tuple(arr[:])) for i in range(start, len(s)): arr.append(i) self.get_all_subsets(i+1, s, arr) arr.pop() return def cutter(self, s, cuts): res = [] for cut in cuts: cut = list(cut) cut = [0] + cut + [len(s)] tmp = [] for i, e in enumerate(cut): if i > 0: tmp.append(s[cut[i-1]:cut[i]]) ct = 0 for t in tmp: if self.check_palindrome(t): ct +=1 if ct == len(tmp): res.append(tmp) if self.check_palindrome(s): res.append([s]) return res def partition(self, s: str) -> List[List[str]]: if not s: return if len(s) == 1: return [s] self._set = set() self.get_all_subsets(0, s, []) return self.cutter(s, self._set) Time complexity Space Complexity O(2^n) O(n)

Challenge Given the head of a linked list, find all the values that appear more than once in the list and delete the nodes that have any of those values. Return the linked list after the deletions. e.g 1 -> 2 ->3 ->2 returns 1 -> 3 Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def print_list(self, head): tmp = head while tmp: print(tmp.val, end=", ") tmp = tmp.next def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode: tmp = head oc = defaultdict(int) while tmp: oc[tmp.val] += 1 tmp = tmp.next tmp = head prev = head while tmp: if oc[tmp.val] > 1 and tmp == head: head = tmp.next prev = head elif oc[tmp.val] > 1: prev.next = tmp.next else: prev = tmp tmp = tmp.next self.print_list(head) return head Solution 2 - Using dummy node def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode: tmp = head oc = defaultdict(int) while tmp: oc[tmp.val] += 1 tmp = tmp.next fake = ListNode() fake.next = head prev = fake tmp = head while tmp: if oc[tmp.val] > 1: prev.next = tmp.next else: prev = tmp tmp = tmp.next return fake.next

Challenge Implement a queue (FIFO) using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty). Solution class MyQueue: def __init__(self): self.stack1 = [] self.stack2 = [] self.mypeek = None def push(self, x: int) -> None: if not self.stack1: self.mypeek = x self.stack1.insert(0, x) return None def pop(self) -> int: while len(self.stack1): val = self.stack1.pop(0) self.stack2.insert(0, val) if self.stack2: ret = self.stack2.pop(0) while len(self.stack2): val = self.stack2.pop(0) self.stack1.insert(0, val) return ret def peek(self) -> int: if self.stack1: self.mypeek = self.stack1[len(self.stack1)-1] return self.mypeek if self.peek else None def empty(self) -> bool: if len(self.stack1) == 0: return True return False

Algo I realized, most of the time, I’m not able to find back my answers from previous coding challenges. I can remember a similar problem or want to have a quick reminder about something and I can’t find it… With this blog, I’m hoping that it will change, I’ll try to keep things nice and tidy. I used to post them on www.blog.nolanemirot.com but I feel it’s more convenient to have another blog for that. ...