Monday, March 23, 2009

Algorithms: Check whether two words are anagrams

Задача: необходимо проверить, являются ли два слова анаграммами.

Для начала давайте вспомним (или узнаем) что такое анаграммы. Итак:

"Анаграмма - литературный приём, состоящий в рекомбинации букв или звуков определённого слова (или нескольких)" или более простой вариант определения "Анаграмма -это перестановка букв, посредством которой из одного слова можно составить другое" (более подробно можно почитать в Википедии).

Итак, есть много (и довольно разных) вариантов решения этой задачи. Раскажу об одном из них. Итак, для начал предположим что у нас слова, которые мы будем сравнивать - находятся в кодировке ASCII. Далее, оба слова необходимо перевести в нижний регистр (для этого можно использовать String.ToLower() ну или придумать свою замену, если посчитаете, что ToLower() может отнимать много времени).

После того как оба слова переведены, можно для первого слова построить "гистограмму" вхождения буквы в слово. Например, у нас есть слово "streaming", следовательно гистограмма для это слова будет выглядеть как

s - 1
t - 1
r - 1
e - 1
a - 1
m - 1
i - 1
n - 1
g - 1

Далее, анализируя второе слово, мы можем уменьшать значения в гистограмме. И на последнем шаге необходимо пробежатся по всем значениям в "гистограмме" и проверить все ли значения равны 0. Если нет - то сравниваемые два слова не анаграммы.

Приведу пример реализации этого алгоритма на C#:

    1 /// <summary>

    2 /// Check whether two words are anagrams.

    3 /// </summary>

    4 /// <param name="value1">First word.</param>

    5 /// <param name="value2">Second word.</param>

    6 /// <returns>True if two specified word are anagrams, otherwise false.</returns>

    7 public static Boolean IsAnagram(String value1, String value2)

    8 {

    9     if (String.IsNullOrEmpty(value1) || String.IsNullOrEmpty(value2) ||

   10         value1.Length != value2.Length)

   11     {

   12         return false;

   13     }

   14 

   15     // convert strings to lowercase.

   16     value1 = value1.ToLower();

   17     value2 = value2.ToLower();

   18 

   19     int[] histogram = new int[256];

   20 

   21     for (int index = 0; index < value1.Length; index++)

   22     {

   23         histogram[value1[index] - 'a']++;

   24     }

   25 

   26     for (int index = 0; index < value2.Length; index++)

   27     {

   28         int charIndex = value2[index] - 'a';

   29         if (histogram[charIndex] == 0)

   30         {

   31             return false;

   32         }

   33 

   34         histogram[charIndex]--;

   35     }

   36 

   37     return true;

   38 }

 

Сложность - O(n).

 

PS: В следующий раз я раскажу как найти все комбинации (не путайте с перестановками) строки.

 

Happy coding...

No comments :

Post a Comment