Оптимизация проверки Ява анаграмма (сравниваем 2 строки)


Анаграмма-это как путаница букв в строке:

кашпо является анаграммой остановить

Вильма является анаграммой ilWma

Я собираюсь через книгу трескать кодирование интервью и в основном строковые манипуляции есть проблема:

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

Мой метод использует StringBuffer вместо string, потому что вы можете .deleteCharAt(индекса) с StringBuffer/StringBuilder по.

public boolean areAnagrams(StringBuffer s1b, StringBuffer s2b) {

    for (int i=0; i<s1b.length(); ++i) {
        for (int j=0; j<s2b.length(); ++j) {

            if (s1b.charAt(i) == s2b.charAt(j)) {

                s1b.deleteCharAt(i);
                s2b.deleteCharAt(j);

                i=0;
                j=0;
            }
        }
    }

    if (s1b.equals(s2b)) {
        return true;
    } else
        return false;

}

Я перебирать каждый символ в s1b и если я найду подходящую char в привод s2b я удалить их обоих из каждой строки и перезапустить цикл (набор я и Джей к нулю), так как длину StringBuffer объектов меняется, когда вы .deleteCharAt(индекс).

У меня два вопроса:

  • Я должен использовать то StringBuilder за StringBuffer (в Java)?
  • Как я могу сделать это быстрее?

В отношении fasterness:

Этот метод хорош тем, что он не требует какого-либо дополнительного пространства, но он вроде уничтожает данные, как вы работаете на нем. Существуют ли какие-либо альтернативы, которые я упустил из виду, что потенциально может сохранить строк, но все же увидеть, если они являются анаграммами без использования слишком много внешней памяти (т. е. копии строк не допускаются -- как вызов)?

И, если вы можете использовать любой тип хранилищ в дополнение к этому, можно снизить время сложность \$О(П)\$ (технически \$о(2Н)\$) вместо \$o(п^2)\$?

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



26256
11
задан 6 апреля 2011 в 10:04 Источник Поделиться
Комментарии
8 ответов

Начните с простой, легкий для понимания вариант. Попробуйте использовать функции API.

import java.util.Arrays;
...

public boolean areAnagrams(String s1, String s2) {
char[] ch1 = s1.toCharArray();
char[] ch2 = s2.toCharArray();
Arrays.sort(ch1);
Arrays.sort(ch2);
return Arrays.equals(ch1,ch2);
}

Конечно, это не самый быстрый способ, но в 99% это "достаточно хорошо", и вы можете увидеть , что происходит. Я бы даже не стал рассматривать жонглировать вещами, как удалил чаров в то StringBuilder, если нет серьезных проблем производительности.

27
ответ дан 7 апреля 2011 в 06:04 Источник Поделиться

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

Для выполнения алгоритма за o(n), то для первой строки, и подсчитать число экземпляров каждой буквы. Затем перебрать вторую строку и сделать то же самое. После этого, убедитесь, что рассчитывает матч.

Чтобы сэкономить немного памяти, использовать тот же массив по обоим пунктам; при переборе первой строки, инкремент после того, как отсчет для каждой буквы. При переборе во-вторых, декремента. После этого, убедитесь, что каждая буква равна нулю.

При выполнении этого алгоритма универсальных наборов объектов, можно хранить на счету в словаре выключает хэш-код объекта. Однако, так как мы используем относительно небольшой алфавит, простой массив будет делать. В любом случае, стоимость хранения составляет O(1).

Рассмотрено следующие псевдо-код:

function 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

15
ответ дан 7 апреля 2011 в 02:04 Источник Поделиться


как я могу сделать это быстрее?

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

Ваш алгоритм О(А * Б) * (А+Б), где А и Б - длины входной строки. Последние (А+Б) два deleteCharAt(...) операций, что делает его в ВСЕ О(N^3) алгоритм. Вы могли принести, что до О(N) (линейная), создав карту частоты строк, и сравнив эти карты.

Демо:

import java.util.HashMap;
import java.util.Map;

public class Main {

public static boolean anagram(String s, String t) {
// Strings of unequal lengths can't be anagrams
if(s.length() != t.length()) {
return false;
}

// They're anagrams if both produce the same 'frequency map'
return frequencyMap(s).equals(frequencyMap(t));
}

// For example, returns `{b=3, c=1, a=2}` for the string "aabcbb"
private static Map<Character, Integer> frequencyMap(String str) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for(char c : str.toLowerCase().toCharArray()) {
Integer frequency = map.get(c);
map.put(c, frequency == null ? 1 : frequency+1);
}
return map;
}

public static void main(String[] args) {
String s = "Mary";
String t = "Army";
System.out.println(anagram(s, t));
System.out.println(anagram("Aarmy", t));
}
}

который печатает:

true
false

6
ответ дан 7 апреля 2011 в 07:04 Источник Поделиться

Я собираюсь ответить на этот немного больше мета:

Увидев этот вопрос я задаю себе: что интервьюер хочет знать от меня?

Он ожидает


  • низкого уровня, оптимизированный алгоритм (как вы пытаетесь)

  • или он хочет видеть, что я могу применить стандартный Java API для проблема (как Landei намекает)

  • или, может быть, что-то между ними, как оптимального внедрения и использования мульти-установка/насчитал набор/мешок (как Барт и Скотт)

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

3
ответ дан 7 апреля 2011 в 08:04 Источник Поделиться

Используя гуава-это Мультимножество, вы можете получить некоторые очень читаемый и лаконичный код:

public static boolean areAnagrams(String s1, String s2) {
Multiset<Character> word1 = HashMultiset.create(Lists.charactersOf(s1));
Multiset<Character> word2 = HashMultiset.create(Lists.charactersOf(s2));
return word1.equals(word2);
}

2
ответ дан 1 февраля 2012 в 06:02 Источник Поделиться

deleteCharAt(индекс) должен тасовать символы после индекса через, так что вы могли бы быть лучше перебирать текст, начиная с конца.

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

1
ответ дан 7 апреля 2011 в 02:04 Источник Поделиться

// in Java this would be an unusual signature
public boolean areAnagrams(StringBuffer s1b, StringBuffer s2b) {

for (int i=0; i<s1b.length(); ++i) {
for (int j=0; j<s2b.length(); ++j) {
// what could you do if the condition evaluates fo false here?
if (s1b.charAt(i) == s2b.charAt(j)) {
// ouch. ask yourself what might be happening inside this JDK method
// best case it bumps an offset, worst case it reallocs the backing array?
s1b.deleteCharAt(i);
s2b.deleteCharAt(j);

// double ouch. one failure mode for fiddling with the loop var would be infinite loop
// avoid this
i=0;
j=0;
}
}
}

// if you have reached this line of code, what else do you know about s1b and s2b?
if (s1b.equals(s2b)) {
return true;
} else
return false;
}

1
ответ дан 8 апреля 2011 в 04:04 Источник Поделиться

Предположим, что мы хотим проверить str1 и str2, если они являются анаграммами или нет

public boolean checkAnagram(String s1 , String s2 ) {
int i=0;
int j=0;

// no need to check if that j < s2.length()
// because the two strings must be that the same length.

while(i < s1.length()) {

if(s1.indexOf(s2.charAt(j) < 0 || s2.indexOf(s1.charAt(i)) < 0 )
return false;

i++;
j++;
} // end of While

return true;
}// end of Check Anagram Method. the Big-Oh is O(n log n)

0
ответ дан 31 января 2012 в 03:01 Источник Поделиться