naive berry
How can I optimize my code on the prompt (image)
Here's the code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**4)
s = input()
t = input()
def check_str(x):
yes = 0
for i in range(len(t)):
if len(x) == yes:
return True
if t[i] == x[yes]:
yes += 1
return len(x) == yes
@lru_cache(None)
def f(i, string):
if i == len(s):
if check_str(string):
return string
return ''
pick = f(i+1, string+s[i])
no_pick = f(i+1, string)
if len(pick) > len(no_pick):
return pick
return no_pick
print(f(0, ''))
The function f(i, string) is for getting all types of combinations of s with it's recursive selection whether we should pick the current character at index i in s or not (those are the two pick and no_pick). The function check_str(x) returns a bool whether the input string x is the "longest subsequence" with string t.
bronze bronze
