Возможно ли получить из одной строки другую с заменой символом по определённым правилам?

Рейтинг: 3Ответов: 2Опубликовано: 27.07.2023

Задача. Вася придумал игру для умного телевизора: можно сколько угодно раз выбрать две произвольные буквы латинского алфавита и заменить в строке все вхождения первой буквы на вторую, а второй — на первую. Так при выборе буквы a и b строка abc превратится в bac. Если выбрать буквы a и x, то строка abc превратится в строку xbc. Цель игры состоит в том, чтобы получить из строки s1 строку s2.

К сожалению, Вася умеет только генерировать гениальные идеи, но не программировать. Он придумал много пар строк s1 и s2. Для каждой пары определите, возможно ли получить из строки s1 строку s2 по правилам игры.

Формат ввода В первой строке задано число t (1 ≤ t ≤ 100) — количество пар строк, придуманных Васей. В следующих 2t строках вводятся t пар слов равной длины, разделенных переводом строки и состоящих из строчных латинских букв — s1 и s2 соответственно.

Гарантируется, что суммарная длина всех слов не превосходит 105 символов.

Формат вывода Для каждой пары слов выведите YES, если из s1 можно получить s2 по правилам игры и NO в противном случае.

Я пробовал делать по-разному. Например, так, как показано ниже. Однако, проходит только один тест (предполагаю, что тот, который и показан). За любые идеи буду очень благодарен. Может быть, какие-то случаи я пропустил?

import re

t = int(input())
s12_list = []
s1_list = []
s2_list = []

for _ in range(2*t):
    s12 = input().split()
    s12_list.append(s12)

for i in range(2*t):
    if i % 2 == 0:
        s1_list.append(s12_list[i])
    else:
        s2_list.append(s12_list[i])

s1_list = re.sub(r"[''\[\] ]", '', str(s1_list))
s2_list = re.sub(r"[''\[\] ]", '', str(s2_list))
s1_list = s1_list.split(',')
s2_list = s2_list.split(',')

for l in range(len(s1_list)):
    for w in range(len(s1_list[l])):
        bufervar1 = s1_list[l][w]
        bufervar2 = s2_list[l][w]
        for r in range(len(s1_list[l])):

            if s1_list[l][r] == s1_list[l][w]:
                s1_list[l] = s1_list[l].replace(s1_list[l][r], str(bufervar2))

for p in range(len(s1_list)):
    if (s1_list[p] == s2_list[p]) == True:
        print('YES')
    else:
        print('NO')
python строки
Источник: Stack Overflow на русском

Ответы

▲ 3Принят

Если я правильно понял задачу, то можно предложить такой вариант. Проверяется однозначность соответствия букв первой и второй строки.

Не помешало бы приведение примеров и ссылки на точное условие и систему проверки, если она свободно доступна.

def check(s, t):
    if len(s) != len(t):
        return  'NO'
    dicts = {}
    dictt = {}
    for pair in zip(s, t):
        if dicts.setdefault(pair[0], pair[1]) != pair[1]:
            return 'NO'
        if dictt.setdefault(pair[1], pair[0]) != pair[0]:
            return 'NO'
    return 'YES'
▲ 0

Исходя из того, что Вася меняет все вхождения двух букв и меньше, значит можно сравнить две строки и если из второй строки исчезло больше двух букв, значит такой вариант невозможен, если исчезли две буквы и меньше, значит возможен.

t = int(input())

for _ in range(t):
    # Считываем первую строку
    s1 = input()
    
    # Считываем вторую строку
    s2 = input()
    
    # Хоть по заданию и сказано, что они равны, на всякий случай выполняем проверку
    if len(s1) != len(s2):
        print('NO')
        continue
    
    # Сравниваем каждую букву в первом наборе с буквой во втором
    # Если набор букв расходится, то запоминаем какая буква поменялась и на какую поменялась
    # Если в результате поменялось больше 2 пар букв, значит такой результат невозможен по условию задачи
    # Для нахождения уникальных букв используем set
    differences = set()
    for i in range(len(s1)):
        if s1[i] != s2[i]:
            differences.add((s1[i], s2[i]))
    
    if len(differences) > 2:
        print('NO')
    else:
        print('YES')