Ошибка алгоритма анаграммы

Возможный дубликат:
алгоритм анаграммы в java

    public static boolean test(String a, String b) {
    a=a.toLowerCase();
    b=b.toLowerCase();
    boolean result = true ;
    boolean tmp1=false;

    if(a.length()==b.length()){
    for(int i=0;i<a.length();i++){
        tmp1=false;
        for(int k=0;k<b.length();k++){
            if(a.charAt(i)==b.charAt(k)){



                return true;
                }

        }
        if(tmp1==false){
            result=false;
            break;
        }
        if(i==a.length()-1)
            result=true;
        }
    }

    else {
        result=false;
        }



    return result;

}

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

Код работает правильно, когда ввод

  • первое слово dsa
  • второе слово асд
  • Вывод - анаграмма (правильный результат)

Код не подходит для ввода

  • первое слово асса
  • второе слово асаа
  • результат - анаграмма (НЕПРАВИЛЬНЫЙ результат)

В чем я виновата?


java algorithm anagram
person Yusuf Bulak    schedule 04.12.2012    source источник
comment
На этой неделе неделя домашних заданий по анаграмме?   -  person durron597    schedule 04.12.2012
comment
Я бы скопировал одно из множества уже доступных решений. Или, по крайней мере, прочитайте их, потому что есть гораздо более простые и эффективные способы сделать это.   -  person Peter Lawrey    schedule 04.12.2012
comment
@PeterLawrey: я бы не стал. В этом нет никакого обучения. Он написал код, определил, что он не работает, и пытается понять, почему. Это хорошо.   -  person Eric J.    schedule 04.12.2012
comment
@ЭрикДж. Он может узнать, что существует O (N ln N) решений с 6 строками кода вместо O (N ^ 2), но без некоторых исследований ОП вряд ли решит это для себя.   -  person Peter Lawrey    schedule 04.12.2012
comment
вернуться к определению анаграммы. обе строки должны иметь одинаковое количество вхождений каждого символа.   -  person UmNyobe    schedule 04.12.2012
comment
@ durron597 .. Перед этим добавьте во всем мире. ;)   -  person Rohit Jain    schedule 04.12.2012

Ответы (3)


arrow_upward
4
arrow_downward

Ваш алгоритм решает, что слово является анаграммой слишком рано — фактически, как только он может сопоставить первую букву первого слова с любой буквой второго слова:

if(a.charAt(i)==b.charAt(k)){
    return true;
}

Самый простой алгоритм обнаружения анаграмм в Java выглядит следующим образом:

person Sergey Kalinichenko    schedule 04.12.2012
comment
+1 В дополнение к этому, если бы он прошел этот цикл for, он неизбежно вернул бы false, поскольку tmp1 никогда не изменяется. - person Andrew Campbell; 04.12.2012
comment
@YusufBulak Строки неизменяемы, их нельзя сортировать. - person Sergey Kalinichenko; 06.12.2012

arrow_upward
1
arrow_downward

Вы позволяете i изменяться от 0 до a.length() и k от 0 до b.length(). Таким образом, обе переменные цикла начинаются с начала соответствующей строки.

Кроме того, во внутреннем цикле вы немедленно возвращаете true для всей функции, если в любой момент какой-либо символ в b соответствует символу в a.

person Sirko    schedule 04.12.2012

arrow_upward
0
arrow_downward

Прежде всего, если вы собираетесь использовать такие операторы, как return true или return false, используйте их последовательно (избавьтесь от boolean result).

Проблема с этим алгоритмом в том, что как только он обнаружит пару одинаковых символов, он вернет true. Чтобы исправить это, попробуйте отсортировать две строки и проверить равенство всех символов (подсказка: Arrays.sort и String.toCharArray).

person jma127    schedule 04.12.2012
comment
Я не хочу делать с массивом символов - person Yusuf Bulak; 06.12.2012