Анаграмма-2

Существует несколько способов проверки возможности получить одно слово перестановкой букв другого. Наиболее просто можно это сделать, отсортировав и сравнив обе строки. Другой способ заключается в подсчете количества вхождения каждой буквы, т.е. в формировании некоторого массива d[ch], в каждом элементе которого храниться количество букв ch исходной строки. Сравнение данных наборов обеих строк даст ответ на поставленный вопрос. Здесь можно использовать лишь один дополнительный такой массив, который следует заполнять следующим образом: пробегая по первой строке и встречая символ ch, увеличивать значение d[ch] на единицу, затем, пробегая по второй строке следует уменьшать соответствующие значения. Тогда в результате в случае совпадения наборов букв мы получим, что каждый элемент массива d равен нулю, если же это не так, то из первой строки невозможно получить вторую перестановкой букв.

Поскольку, согласно заданию, должны изменить положение все буквы, то необходимо дополнительно проверить условие: нет ли одинаковых букв в исходных строках, стоящих в одной и той же позиции. Если для некоторого k получится, что s1[k]=s2[k], то следует выводить «NO».

Алгоритмическая реализация:

  read(s1,s2)

  if(len(s1)=len(s2))
    for i=1..len(s1)
      if(s1[i]=s2[i]){
        write(’NO’)
        exit
      }

  sort(s1); sort(s2) 
  if(s1=s2) write(’YES’) else write(’NO’)

[Обсуждение] [Все попытки] [Задача]