Проверить, являются ли две строки анаграммой

Я хочу вернуть true, если строка t является анаграммой s. Я поместил все символы s в стек и сравниваю каждый символ t с верхним элементом в стеке, если символ совпадает, я выполняю операцию pop. Если в конце стек пуст, это означает, что строка t является анаграммой строки s. Вот мой код -

public boolean isAnagram(String s, String t) {
    char[] charArray1 = s.toCharArray();
    char[] charArray2 = t.toCharArray();
    if (s.length() != t.length())
    {
        return false;
    }
    Stack<Character> newStack = new Stack<Character>();
    for (int i=0; i<charArray1.length;i++)
    {
        newStack.push(charArray1[i]);
    }
    for (int j=0;j<charArray2.length;j++)
    {
        if(charArray2[j] == newStack.peek())
        {
            newStack.pop();
        }
    }
    if (newStack.isEmpty())
    {
        return true;
    }
    else
    return false;
}



error: s= "abc", t= "bac", Doesn't seem to declare these two strings as anagram

stack algorithm array-algorithms anagram
person ComplexData    schedule 13.02.2017    source источник
comment
Отсортируйте символы в строке в алфавитном порядке, затем сравните   -  person samgak    schedule 14.02.2017
comment
@samgak Приведенная выше логика должна работать, даже если строки не отсортированы,   -  person ComplexData    schedule 14.02.2017
comment
Почему вы хотите использовать стек?   -  person samgak    schedule 14.02.2017

Ответы (2)


arrow_upward
3
arrow_downward

Стек является неправильной структурой данных для этой проблемы, потому что peek() просматривает только верхний элемент стека, а вы хотите проверить, можно ли найти каждый символ в charArray2 где-нибудь в charArray1. Более простой подход — отсортировать массивы, а затем сравнить их как Strings:

public boolean isAnagram(String s, String t) {
    char[] charArray1 = s.toCharArray();
    char[] charArray2 = t.toCharArray();
    Arrays.sort(charArray1);
    Arrays.sort(charArray2);
    String string1 = new String(charArray1);
    String string2 = new String(charArray2);
    return string1.contentEquals(string2);
}
person samgak    schedule 13.02.2017

arrow_upward
2
arrow_downward

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

Использовать сортировку:

1) Отсортировать обе строки
2) Сравнить отсортированные строки

"Or"

Подсчитайте символы и сохраните их в массиве:

Этот метод предполагает, что набор возможных символов в обеих строках невелик. В следующей реализации предполагается, что символы хранятся с использованием 8 бит, и может быть 256 возможных символов.
1) Создайте массивы счетчиков размером 256 для обеих строк. Инициализировать все значения в массивах счетчиков как 0.
2) Перебрать каждый символ обеих строк и увеличить количество символов в соответствующих массивах счетчиков.
3) Сравнить массивы счетчиков. Если оба массива счетчиков одинаковы, верните true.

person GorvGoyl    schedule 13.02.2017