commit 4a255da271b67eeb8b8da3e0d37beeff2f148f33
parent 69371fbc320a52a080ef462ffc2148fbeb2102b4
Author: Andrew Laack <andrew@laack.co>
Date: Tue, 1 Jul 2025 08:48:54 -0500
Completed a few more problems (daily + trie + backtracking)
Diffstat:
5 files changed, 150 insertions(+), 0 deletions(-)
diff --git a/combination-sum-ii/combination-sum-ii.py b/combination-sum-ii/combination-sum-ii.py
@@ -0,0 +1,29 @@
+class Solution:
+ def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
+ candidates.sort()
+ return find_all([], target, candidates, 0, set())
+
+def find_all(current, target, candidates, index, used):
+
+ if str(current) in used:
+ return []
+ else:
+ used.add(str(current))
+
+ if target == 0:
+ return [current]
+
+ ret_ls = []
+
+ while index < len(candidates) and candidates[index] <= target:
+
+ copy_ls = current.copy()
+ copy_ls.append(candidates[index])
+
+ ret = find_all(copy_ls, target - candidates[index], candidates, index + 1, used)
+
+ ret_ls.extend(ret)
+
+ index += 1
+
+ return ret_ls
diff --git a/find-original-typed-string-i/find-original-i.py b/find-original-typed-string-i/find-original-i.py
@@ -0,0 +1,42 @@
+# idea:
+
+# get the counts of each character
+# the total number of possible strings is
+# the number of 2 selections of characters that result in a
+# different word.
+
+# the counting approach likely won't work because it doesn't
+# handle duplicate strings correctly, as is the case with 'aaa'
+# which can only become 'a' or 'aa' but not 'aa' and 'aa'.
+
+# recursive approach:
+ # given the word we create a count branch
+ # every time the current character is the same as the previous
+ # at each branch we continue on assuming it is either their or not
+# how do we handle duplicates then?
+ # to handle duplicate we could memoize but that's slow
+ # we could also skip any character that is a run
+ # and then evaluate all unique selections of it at the end
+ # this runs in linear time and should be simple to do
+
+class Solution:
+
+ def possibleStringCount(self, word: str) -> int:
+ return recurse(word, 0)
+
+def recurse(word, idx) -> int:
+
+ if idx == len(word):
+ return 1
+
+ duplicates = 1
+
+ while idx < len(word) - 1 and word[idx] == word[idx + 1]:
+ duplicates += 1
+ idx += 1
+
+ word_count = duplicates - 1
+
+ word_count += recurse(word, idx + 1)
+
+ return word_count
diff --git a/implement-trie/trie.py b/implement-trie/trie.py
@@ -0,0 +1,57 @@
+class TreeNode():
+ def __init__(self):
+ self.is_string = False
+ self.chars = {}
+
+class Trie:
+
+ def __init__(self):
+ self.root = TreeNode()
+
+ def insert(self, word: str) -> None:
+ current = self.root
+
+ for char in word:
+
+ if not char in current.chars:
+ new_node = TreeNode()
+ current.chars[char] = new_node
+ current = new_node
+ else:
+ current = current.chars[char]
+
+ current.is_string = True
+
+ def search(self, word: str) -> bool:
+
+ current = self.root
+
+ for char in word:
+ if char in current.chars:
+ current = current.chars[char]
+ else:
+ return False
+
+ return current.is_string
+
+ def startsWith(self, prefix: str) -> bool:
+ current = self.root
+
+ for char in prefix:
+ if char in current.chars:
+ current = current.chars[char]
+ else:
+ return False
+ return True
+
+
+# Your Trie object will be instantiated and called as such:
+# obj = Trie()
+# obj.insert(word)
+# param_2 = obj.search(word)
+# param_3 = obj.startsWith(prefix)
+
+# idea:
+# route through the tree based on the prefix of the string.
+# if a string exists, we then mark the node with a 'is_string' bool
+#
diff --git a/remove-duplicates-from-sorted-array/remove-duplicates.py b/remove-duplicates-from-sorted-array/remove-duplicates.py
@@ -0,0 +1,16 @@
+class Solution:
+ def removeDuplicates(self, nums: List[int]) -> int:
+
+ current_index = 0
+ current_val = nums[0] - 1
+
+ for i in range(0, len(nums)):
+
+ if current_val == nums[i]:
+ continue
+
+ current_val = nums[i]
+ nums[current_index] = nums[i]
+ current_index += 1
+
+ return current_index
diff --git a/single-number/single-number.py b/single-number/single-number.py
@@ -0,0 +1,6 @@
+class Solution:
+ def singleNumber(self, nums: List[int]) -> int:
+ xor = 0
+ for num in nums:
+ xor ^= num
+ return xor
