Skip to content

Instantly share code, notes, and snippets.

@orsinium

orsinium/max_subset.py

Created May 4, 2017 18:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save orsinium/2554eeec1b494c7d8e73ca1509c8e6ac to your computer and use it in GitHub Desktop.
Save orsinium/2554eeec1b494c7d8e73ca1509c8e6ac to your computer and use it in GitHub Desktop.
Download ZIP
Find maximal mutual subset in 2 sets.
Raw
max_subset.py
def f(s1, s2):
if not s1 or not s2:
return ''
elif s1[-1]==s2[-1]:
return f(s1[:-1], s2[:-1]) + s2[-1]
else:
return max((f(s1[:-1],s2), f(s1, s2[:-1])), key=len)
if __name__ == '__main__':
while 1:
print(f(input('1: '), input('2: ')))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment