leetcode-prob960

prob960.py

import numpy as np
from functools import lru_cache

def CompareTwoColumns(x, y):
    return np.all(y >= x)

__CACHE = {}

def Solve(prefix, suffix):
    global __CACHE
    key = (prefix.tobytes(), suffix.tobytes())
    if key in __CACHE:
        return __CACHE[key]

    if suffix.size == 0:
        return prefix
    
    solution1 = Solve(prefix, suffix[:, 1:])
    solution2 = prefix
    if prefix.size > 0:
        if CompareTwoColumns(prefix[:, -1], suffix[:, 0]):
            new_prefix = np.concatenate([prefix, suffix[:, :1]], axis=1)
            solution2 = Solve(new_prefix, suffix[:, 1:])
    else:
        new_prefix = np.concatenate([prefix, suffix[:, :1]], axis=1)
        solution2 = Solve(new_prefix, suffix[:, 1:])

    if solution1.shape[1] > solution2.shape[1]:
        final = solution1
    else:
        final = solution2
    __CACHE[key] = final
    return final
        
class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        global __CACHE
        __CACHE = {}
        X = np.array([list(row) for row in A])        
        solution = Solve(np.empty(shape=(X.shape[0], 0)), X)
        return X.shape[1] - solution.shape[1]