theabbie

class Solution:
    def knapsack(self, knapsack, target, i, n):
        if target < 0:
            return -1
        if i >= n:
            return 0
        key = (i, target)
        if key in self.cache:
            return self.cache[key]
        a = 1 + self.knapsack(knapsack, target - knapsack[i], i + 1, n)

theabbie

from collections import defaultdict

class Solution:
    def makeSeg(self, arr, i, j):
        seg = self.seg
        if (i, j) in seg:
            return seg[(i, j)]
        if i == j:
            seg[(i, j)] = arr[i]
            return arr[i]

theabbie

import random

def partition(arr, k):
    n = len(arr)
    i = -1
    for j in range(n):
        if arr[j] <= k:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    return i

theabbie

from collections import defaultdict

class Solution:
    def DFS(self, graph, node, v, s):
        v.add(node)
        for j in graph[node]:
            if j not in v:
                self.DFS(graph, j, v, s)
        s.append(node)
    

theabbie

class Solution:
    def first_missing_positive(self, a):
        a = set(a)
        a.add(0)
        for i in range(1, max(a) + 2):
            if i not in a:
                return i

theabbie

class Solution:
    def product_exclude_itself(self, nums):
        n = len(nums)
        l = [1]
        r = [1]
        for i in range(n):
            l.append(l[-1] * nums[i])
            r.append(r[-1] * nums[n - i - 1])
        return [l[i] * r[n - i - 1] for i in range(n)]
      

theabbie

class Solution:
    def isLCP(self, strs, k):
        return len(set([s[:k] for s in strs])) == 1

    def longest_common_prefix(self, strs):
        n = len(strs)
        if n == 0:
            return ""
        beg = 0
        end = min([len(s) for s in strs])

theabbie

class Solution:
    def getPos(self, board, i, j):
        pos = set(map(str, range(1, 10)))
        ci, cj = i - i % 3, j - j % 3
        for a in range(3):
            for b in range(3):
                if board[ci + a][cj + b] != "." and board[ci + a][cj + b] in pos:
                    pos.remove(board[ci + a][cj + b])
        for a in range(9):
            if board[i][a] in pos:

theabbie

# There is a fence with n posts, each post can be painted with one of the k colors.
# You have to paint all the posts such that no more than two adjacent fence posts have the same color.
# Return the total number of ways you can paint the fence.

from functools import lru_cache

class Solution:
    @lru_cache(maxsize=None)
    def ways(self, a, b, p, n, k):
        if p == n:

theabbie

class Solution:
    """
    @param: strs: a list of strings
    @return: encodes a list of strings to a single string.
    """
    def encode(self, strs):
        _delim = "!@#$%^&*"
        delim = _delim
        check = "".join(strs)
        i = 1