Найти, если 2 строки являются анаграммами в пространстве O (1) и времени O (n)

Question

Вы можете определить, являются ли 2 строки анаграммами после сортировки обеих строк за время O (nlogn), однако возможно ли найти его за время o (n) и пространство O (1).

Answer 1

Абсолютно нет эксперта здесь ...

Но почему бы не просмотреть каждую строку и просто посчитать, сколько раз каждая буква появляется.

При соответствующей реализации это не должно занять большечем O (N) время.

Answer 2

---

Есть несколько способов ее решить.

Метод 1 - Использование функции пользовательского хеш-кода
У нас может быть функция hashCode, например:

static int[] primes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
static String alphabet = "abcdefghijklmnopqrstuvwxyz";


public static int hashCode(String s){
    int sum = 0;

    for(char c: s.toCharArray()){
      sum += primes[c-97];
    }
    return sum;
}

Генерирует хэш обеих строк, и, если хэш-код совпадает, строки являются анаграммами. Этот метод похож на решение, упомянутое Джином, так как он в некотором роде генерирует hashCode для строки.
Временная сложность - O (n)

Метод 2 - Использование хэш-карты символов и целых чисел
Рассмотрим 2 строки как 2 массива символов. Пройдите по первому массиву, добавьте символ в hashmap из char и count, увеличивайте количество, когда вы найдете символ. Аналогичным образом просмотрите второй массив, уменьшите счетчик в хэш-карте или, если вы не нашли символ, они не являются анаграммами. Наконец, когда карта содержит все символы и считается как 0, тогда снова 2 строки являются анаграммами.

Метод 3 - Использовать массив count (мой любимый)

<code>
boolean are_anagrams(string1, string2){
 
    let counts = new int[26];
 
    for each char c in lower_case(string1)
        counts[(int)c]++
 
    for each char c in lower_case(string2)
        counts[(int)c]--
 
    for each int count in counts
        if count != 0
            return false
 
    return true
}

Вы можете получить все коды здесь .

Answer 3

генерирует массив простых чисел [26], каждое простое число представляет символ, затем, когда вы пересекаете строку, умножаете простое число каждого символа, если оно равно, это анаграммы, иначе нет. занимает O (n) и постоянное пространство

Answer 4

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

let h => hash which maps letters to occurence_count (initialized to 0)

for each letter l in string a
  h[l] = h[l] + 1
end

for each letter l in string b
  h[l] = h[l] - 1
end

for each key l in h 
  return false if h[l] != 0
end

return true

Это будет выполняться в O (n) + O (n) + c = O (п) .Наш хэш содержит 26-буквенные пятна, каждое из которых связано с целым числом.Таким образом, пробел равен O (26) = O (1)

[[Edit]] , так же, как указано выше, но с аннотациями анализа времени:

let h => hash which maps letters to occurence_count (initialized to 0)

#this loop runs n times
for each letter l in string a
  #hash lookups / writes are constant time
  h[l] = h[l] + 1
end
#above function ran O(n) time

for each letter l in string b
  h[l] = h[l] - 1
end

#runs in O(alphabet) = O(c) = constant-time
for each key l in h 
  return false if h[l] != 0
end

return true

Answer 5

unsigned char CharacterCheck(char item)
{

    if ((item >= 'A') && (item <= 'Z'))
        return (item - 'A');

    if ((item >= 'a') && (item <= 'z'))
        return ((item - ('a' - 'A')) - 'A');

    return -1;

}

unsigned char AnagramCheck6 (char * item1, char * item2)
{
    char *test                      = item1;
    char *test2                     = item2;
    int count                       = 0;
    unsigned char rc                = 0;
    unsigned char rslt              = 0;

    while (*test && *test2)
    {
        rslt = CharacterCheck(*test++);

        if (rslt != 0xff)
            count += rslt;

        rslt = CharacterCheck(*test2++);

        if (rslt != 0xff)
            count -= rslt;
    }

    if (*test)
    {
        while (*test)
        {
            rslt = CharacterCheck(*test++);

            if (rslt != 0xff)
                count += rslt;
        }
    }

    if (*test2)
    {
        while (*test2)
        {
            rslt = CharacterCheck(*test2++);

            if (rslt != 0xff)
                count -= rslt;
        }
    }

    if (count)
        rc = 1;

    return rc;

}

Следующий фрагмент проверяет правильность символа и преобразует регистр в случае необходимости. Вторая и третья проверки учитывают, если строки имеют разную длину

Answer 6

Выполнить в: O(n) + O(n) = O(n)

Исправить используемое пространство: O(256) = O(1)

Вот код на Java

private static boolean isAnagramWithOneArray(String strFirst, String strSecond) {
    int[] charsCount = new int[256];

    if (strFirst != null && strSecond != null) {
        if (strFirst.length() != strSecond.length()) {
            return false;
        }
        for (int i = 0; i < strFirst.length(); i++) {
            charsCount[strFirst.charAt(i)]++;
            charsCount[strSecond.charAt(i)]--;
        }
        for (int i = 0; i < charsCount.length; i++) {
            if (charsCount[i] != 0) {
                return false;
            }
        }
        return true;
    } else {
        return (strFirst == null && strSecond == null);
    }
}

Answer 7

я бы сделал что-то, как показано ниже:

//is s an anagram of t?
#include <string>

bool is_anagram(const string& s, const string& t)
    {
    bool ret = false;

    //if s and t are anagrams, they must of same size
    if( s.length() != t.length() )
        {
        return ret;
        }

        //assume that s and t have valid ascii characters only
    char letters[ 256 ] = {0};
    int i;

    // find occurence of each character in string s
    for( i = 0; i < s.length(); i++ )
        {
        (letters[ s[i] ])++;
        }

    // now, find occurence of each character in string t, but decrement 
    // correspnding character
    for( i = 0; i < t.length(); i++ )
        {
        //if the count is <0 means the given character is not present in s
        if( --(letters[ t[i] ]) < 0 ) 
            {
            return ret;
            }
        }

    //out of for loop means success
    ret = true;
    return ret;
    }

Answer 8

Все предложения здесь, как правило, используют один и тот же подход для сортировки входных строк и последующего сравнения результатов.Будучи в основном заинтересованными в регулярных письмах ascii, это можно оптимизировать путем сортировки счетчиков, что кажется подходом большинства ответчиков.Сортировка счетчиков может выполнять сортировку ограниченного алфавита чисел / целых чисел в O (n), поэтому технически это правильные ответы.Если мы должны учесть время для обхода массива счетчиков, то оно будет включать время для алфавита, что делает O (m + n) несколько более правильной верхней границей в случаях, когда алфавит является UTF-32.

Я склонен думать, что наиболее общий правильный подход потребует O (n lg n), поскольку быстрая сортировка может оказаться быстрее в реальном времени в случае, если алфавит не может быть достаточно ограничен.

Answer 9

приведенный выше код не будет работать во всех условиях

, поэтому мы можем быстро отсортировать массив и сравнить его при выделении пробелов

Answer 10

Может быть что-то вроде:

    String str1 = "test";
    String str2 = "tzet";
    int count = 0;
    for (int i = 0; i < str1.length(); i++)
    {
        count = count + str1.charAt(i) - str2.charAt(i);
    }
    System.out.println(count);

Вычесть каждый символ из строки 2 и добавить каждый символ из строки 1 для подсчета (при условии символов ASCII).Если они анаграммы, количество будет равно нулю.

Это не относится к анаграммам с вставленными пробелами.