Нужно вычислить тип совпадения строки В и строки А

Question

Есть строки A — название стартапа Алисы и строка B — название стартапа Зелибобы. Обе строки имеют одинаковую длину N. Для каждой позиции строки B, нужно вычислить тип совпадения в этой позиции со строкой A. Если Вi=Аi, то в позиции i тип совпадения должен быть равен Р (от слова plagiarism). Если Вi != Аi, но существует другая позиция , такая что Вi=Аj, то в позиции i тип совпадения должен быть равен S (от слова suspicious).

Важно: • Буквы в рамках одной строки могут повторяться. • Каждую букву строки A можно использовать не более чем в одном совпадении типа plagiarism или suspicious. • Предпочтение всегда отдается типу plagiarism. • В случае совпадения типа suspicious, предпочтение всегда отдается самой левой позиции в строке A. В остальных позициях тип совпадения должен быть равен I (от слова innocent).

TEST 1
Ввод       Вывод
CLOUD      PSIIP
CUPID

TEST 2
Ввод       Вывод
ALICE      SPPII
ELIBO

TEST 3
Ввод         Вывод
ABCBCYA      IPSSPIP
ZBBACAA**

Мой код:

def main(a, b):
    res = ''
    n = len(b)
    for i in range(n):
        if b[i] == a[i]:
            res += 'P'

        elif b[i] != a[i]:
            if b[i] in a:
                res += 'S'
            else:
                res += 'I'
    return res

print(main('CLOUD', 'CUPID'))
print(main('ALICE', 'ELIBO'))
print(main('ABCBCYA', 'ZBBACAA'))

Выводит: PSIIP, SPPII, IPSSPSP

Answer 1

Интересный вопрос. Но мне кажется за один цикл решить его нельзя, так как ошибка как раз и происходит из-за невозможности предсказать P в конце.

Поэтому мое решение (может не настолько же элегантное) но в первом цикле помимо отметки совпадений сохраняет статистику по буквам чтобы потом их попарно объединять если получиться во втором цикле вызывающем дважды set_I_or_S для каждой не выясненной позиции.

Все пункты условий соблюдаются, а что касается кода то set_I_or_S можно переписать с return при желании, ну или вообще код написать иначе используя эту же идею.

def main(a, b):
    res = ['?'] * len(b) # массив с нужным размером
    ad = {}  # для подсчета количества букв
    bd = {}  # для подсчета количества букв
    for i in range(len(b)):
        if (b[i] == a[i]):
            res[i] = 'P'
        else: # считаем буквы в обоих словах
            bd[a[i]] = ( bd[a[i]] if a[i] in bd else 0 ) + 1
            ad[b[i]] = ( ad[b[i]] if b[i] in ad else 0 ) + 1

    for i in range(len(b)):
        if (res[i] == '?'):
            set_I_or_S(b[i], bd, i, res)
            set_I_or_S(b[i], ad, i, res)

    return ''.join(res)

def set_I_or_S(letter, dictionary, i, res):
    if (letter in dictionary and dictionary[letter] != 0):
        dictionary[letter] -= 1 # вычитаем букву из словаря
        # S если буква была в предыдущем словаре иначе I
        res[i] =  'I' if res[i] == '?' else 'S'

def test(a, b, c):
    res = main(a, b)
    compare = res == c
    print(res, compare)

test('CLOUD', 'CUPID', 'PSIIP')
test('ALICE', 'ELIBO', 'SPPII')
test('ABCBCYA', 'ZBBACAA', 'IPSSPIP')

Выводит: PSIIP True, SPPII True, IPSSPIP True

Answer 2

Могу предложить такое решение:
В первом цикле проставляем буквы P. а во втором бежим по индексам, которые мы еще не проверяли для строки b, и для строки a.
При этом для строки b мы создаем список нужных индексов единожды (исключаем буквы P), а для строки a - каждую итерацию цикла по строке b для обновления списка уже проверенных символов.
Для каждого индекса из строки a происходит проверка на совпадение b[i]==a[j] и если ни один символ для текущего i не совпадает - пишем I.

def check(a, b):
    res = [' ']*len(a)
    used = set()
    for i in range(len(b)):
        if b[i]==a[i]:
            res[i] = 'P'
            used.add(i)

    for i in sorted(set(range(len(b))) - used):
        for j in sorted(set(range(len(a))) - used):
            if b[i]==a[j]:
                res[i] = 'S'
                used.add(j)
                break
        else:
            res[i] = 'I'

    return ''.join(res)

def test(a, b, c):
    res = check(a, b)
    assert res==c
    print(res)

test('CLOUD', 'CUPID', 'PSIIP')
test('ALICE', 'ELIBO', 'SPPII')
test('ABCBCYA', 'ZBBACAA', 'IPSSPIP')

БЛОГ НА HUSL

Нужно вычислить тип совпадения строки В и строки А

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