количество букв, которое нужно удалить из строки, чтобы оно делилось на другую строку - PullRequest
Новая
       12

количество букв, которое нужно удалить из строки, чтобы оно делилось на другую строку

0 голосов
/ 30 мая 2019

Я делаю эту проблему https://www.spoj.com/problems/DIVSTR/

Нам даны две строки S и T. S делится на строку T, если существует некоторое неотрицательное целое число k, удовлетворяющее уравнению S = k * T

Какое минимальное количество символов должно быть удалено из S, чтобы S делилось на T?

Основная идея состояла в том, чтобы сопоставить T с S с помощью указателя и подсчитать количество экземпляров T, встречающихся в S, когда подсчет завершен, перенести указатель в начало T и, если есть несоответствие, сравнить первую букву T с настоящим письмом С.

Этот код прекрасно работает с предоставленными ими тестовыми примерами и пользовательскими тестовыми примерами, но он не смог пройти через скрытые тестовые примеры.

это код 

def no_of_letters(string1,string2):
#     print(len(string1),len(string2))
    count = 0 
    pointer = 0
    if len(string1)<len(string2):
        return len(string1)
    if (len(string1)==len(string2)) and (string1!=string2):
        return len(string1)
    for j in range(len(string1)):
        if (string1[j]==string2[pointer]) and pointer<(len(string2)-1):
            pointer+=1
        elif (string1[j]==string2[pointer]) and pointer == (len(string2)-1):
            count+=1
            pointer=0
        elif (string1[j]!=string2[pointer]):
            if string1[j]==string2[0]:
                pointer=1
            else:
                pointer = 0
    return len(string1)-len(string2)*count

Единственное место, где, как мне кажется, должна быть путаница, это когда одни и те же буквы могут быть частями двух пунктов, но это не должно быть проблемой, потому что наш ответ не должен принимать во внимание дублирование.

например, S = 'akaka' T = 'aka' даст выход 2, независимо от того, будет ли первый 'aka', ka считать или вторым ak, 'aka'.

1 Ответ

1 голос
/ 31 мая 2019

Я считаю, что решение намного проще, чем вы его делаете. Вы просто пытаетесь определить, сколько раз символы T появляются по порядку в S. Все остальное - это символы, которые вы удаляете. Например, учитывая пример RobertBaron S="akbaabka" и T="aka", вы должны написать свою подпрограмму, чтобы найти символы a, k, a, в том порядке , с начала S 

akbaabka
ak a^
# with some pointer, ptr, now at position 4, marked with a caret above

После этого вы можете повторить остаток строки: 

find_chars(S[ptr:], T)

При каждом вызове вы ищите T в S; если вы найдете его, сосчитайте 1 повторение и повторите остаток от S; если нет, вернуть 0 (базовый случай). По мере того, как вы ползете обратно в свой стек рекурсии, накапливайте все 1 числа, и ваше значение равно k.

Количество символов для удаления составляет len(s) - k*len(T).

Можете ли вы взять его оттуда?

...