Проблема с функцией bool - всегда возвращает true?

Question

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cstdio>

using namespace std;

static bool isanagram(string a, string b);

int main(void)
{
    int i,n,j,s;
    cin >> n;
    string a, b;
    cin >> a >> b;
    if(!isanagram(a,b)) cout << "False" << endl;
    else cout << "True" << endl;
    return 0;


}

static bool isanagram(string a, string b)
{
    int i, j, size, s=0;
    size = a.size();
    bool k;
    for(i=0;i<size;i++)
    {
        k=false;
        for(j=0;j<size;j++)
        {
            if(a[i] == b[j]) { k = true; break; }
        }
        if(k==true) s+=1;
    }
    cout << a[2] << b[2] << endl;
    if(s == size) return true;
    else return false;

}

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

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

Заранее спасибо.

Answer 1

Логика вашей функции isanagram фатальна - она ​​никогда не будет работать правильно, даже если вам удастся исправить ошибки в ней.

Вы должны убедиться, что у вас есть правильный алгоритм, прежде чем начать кодирование. Один простой алгоритм может быть:

• сортировка
• сортировка b
• isanagram = (a == b)

Answer 2

Не всегда возвращается истина:

Вот мой ввод:

0
sdf 
fda

Вот вывод, который я получил:

fa 
False

Относительно вашей задачи: если производительность не является проблемой для вашей задачи, просто отсортируйте 2 строки (используя std :: sort) и сравните результаты.

Относительно вашего стиля:

• используйте string :: length () вместо size () - это более идиоматично
• вместо if(s == size) return true; else return false; рассмотрим return s == size
• передать ваши строки по константной ссылке, а не по значению
• рассмотреть возможность объявления переменных как можно ближе к точке их использования (но не близко) и инициализировать их при объявлении (i, j, k, size все подходят под эту подсказку)

Answer 3

Ваш подход в порядке, но у него есть небольшой недостаток. Вы гарантируете, что каждый символ из строки a присутствует в строке. Поэтому, если a = "aab" и b = "abc", ваш подход пометит их как анаграмму. Вы также должны принять во внимание количество символов в учетной записи.

Определение анаграммы :

Анаграмма - это тип игры слов, результат перестановки букв слова или фразы для получения нового слова или фразы, используя все оригинальные буквы ровно один раз ;

Самый простой способ, который предложили многие, - убедиться, что строки одинаковой длины. Если они есть, отсортируйте две строки и проверьте равенство.

Если вы хотите пропатчить свой подход, вы можете сделать символ в строке b NULL после того, как он будет сопоставлен с символом в строке a.

Что-то вроде:

if(a[i] == b[j]) { b[j] = 0; k = true; break; }

вместо вашего:

if(a[i] == b[j]) { k = true; break; }

Таким образом, после сопоставления символа b он не может участвовать снова.

Answer 4

Существуют два способа проверки анаграмм:

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

2. Подсчитайте частоту каждого char в каждой строке. Если они анаграммы, то значения частоты для каждого char будут одинаковыми для обеих строк.

Answer 5

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

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

Давайте сделаем это просто:

bool anagram(std::string const& lhs, std::string const& rhs)
{
  if (lhs.size() != rhs.size()) return false; // does not cost much...

  std::vector<int> count(256, 0); // count of characters
  for (size_t i = 0, max = lhs.size(); i != max; ++i)
  {
    ++count[lhs[i]];
    --count[rhs[i]];
  }

  for (size_t i = 0, max = count.size(); i != max; ++i)
    if (count[i] != 0) return false;

  return true;
} // anagram

Давайте посмотрим на это: anagram("abc","cab")

1. Инициализация: count = [0, 0, ...., 0]
2. Первый цикл i == 0> ['a': 1, 'c': -1]
3. Первый цикл i == 1> ['a': 0, 'b': 1, 'c': -1]
4. Первый цикл i == 2> ['a': 0, 'b': 0, 'c': 0 ]

И второй цикл пройдет без проблем.

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

int main(int argc, char* argv[])
{
  if (argc != 3) std::cout << "Usage: Program Word1 Word2" << std::endl;
  else std::cout << argv[1] << " and " << argv[2] << " are "
                 << (anagram(argv[1], argv[2]) ? "" : "not ")
                 << "anagrams" << std::endl;
}

Answer 6

Я вижу некоторые проблемы с вашим кодом. В основном алгоритм неверен. Он будет соответствовать символам в a.size (). Он не учитывает дубликаты (в a или b).

По сути, вы должны отсортировать строки и сравнить их на равенство.

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