Задача на строки - привести к общему

Question

Есть 2 строки, например, cat и concatenate. Какое минимальное число букв в сумме надо выбросить из обоих строк, чтобы остатки строк стали равны.

В примере из cat ничего выбрасывать не надо, из concatenate - 8 букв. Ответ 8. Буквы можно выбрасывать из любой позиции, но переставлять буквы нельзя. Предполагается, что задача может быть решена за 10-15 минут.

Кто может подсказать алгоритм, желательно с кодом, желательно на Питоне.

И еще. Есть ли какие-то материалы, курсы, где рассматриваются подобные задачи. Желательно на русском.

Answer 1

len_str1 = len(str1)
len_str2 = len(str2)
if len_str1 >= len_str2:
    x = len_str1 - len_str2
else:
    x = len_str2 - len_str1
print(f"Ответ: {str(x)} букв}

str1 и str2 - строки.

Answer 2

В случае если необходимо сделать из 1 строки другую - можно сделать так:

str1 = "cat"
str2 = "thisisacat"
if str1 in str2:
    str2 = str2.replace(str1, '')
    res = len(str2)
else:
    str1 = str1.replace(str2, '')
    res = len(str1)
print(f'Ответ: {str(res)}')

Answer 3

вот тут http://coders.ask-ru.net/алгоритм-поиска-длины-наибольшей-общ все есть - с кодом на Питоне
пока что сам придумал такое. Наверняка есть дыры, но несколько тестов вполне проходит

def nopp(s1,s2):
      r1,t1 = mistr_(s1,s2)
      r2,t2 = mistr_(s2,s1)
      tmp = len(s1) + len(s2)
      if r1 > tmp: r1=tmp
      if r2 > tmp: r2=tmp
      if r1 < r2 : 
        print(t1)
        return r1
      else:
        print(t2) 
        return r2

def mistr_(s1,s2):
  res = 0
  tst=''   # what is common
  for i in s1:
    tmp = s2.find(i)
    if tmp == -1: 
      res+=1 # no
      #print('no=',i,res)
    else:
      tst = tst + i
      res+=tmp # begin of s2 before i
      if tmp+1 == len(s2): s2=''  # s2 is finished
      else: s2 = s2[tmp+1:]       # rest of s2 
      #print('yes=',i,'res=',res,'s2=',s2)
  #print(tst)    
  return (res + len(s2),tst)

БЛОГ НА HUSL

Задача на строки - привести к общему

Ответы (3 шт):