Форум программистов, компьютерный форум CyberForum.ru

Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми? - C++

Восстановить пароль Регистрация
 
Zyfchik
0 / 0 / 0
Регистрация: 14.09.2012
Сообщений: 10
18.02.2013, 14:25     Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми? #1
F. Заданы две строки А и В. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми?
Выведите "Yes", если можно переставить буквы в одном из слов, чтобы слова стали одинаковыми или "No" иначе.
F.in
bca
cba
F.out Yes
F.in
ada
dada
F.out No
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.02.2013, 14:25     Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми?
Посмотрите здесь:

вывести из строки те слова ,которые содержат две буквы z. C++
Обработать строку так, чтобы чтобы в ней остались только те слова которые содержат буквы и цифры C++
C++ Преобразовать строку так, чтобы буквы каждого слова были остортированы по возрастанию
Преобразуйте массив так, чтобы все положительные элементы массива стали отрицательными и наоборот C++
Файловый ввод/вывод. Во всех словах строки переставить все входящие буквы «а» в начало слова, а буквы «я» – в конец C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
18.02.2013, 16:39     Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми? #2
Например, упорядочить подсчетом, раз уж только "буквы", и сравнить получившиеся строки. В качестве оптимизации, если строки не равны по длине, вывести No.
akk
 Аватар для akk
44 / 44 / 7
Регистрация: 28.01.2012
Сообщений: 341
18.02.2013, 16:43     Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми? #3
Можно сделать лексикографический анализ, т. е. одно первое слово распарсить в бинарное дерево, а потом с обходом его сравнить символы со вторым словом. Но программировать это для меня еще через чур сложно
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
18.02.2013, 16:53     Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми? #4
Цитата Сообщение от akk Посмотреть сообщение
Можно сделать лексикографический анализ, т. е. одно первое слово распарсить в бинарное дерево, а потом с обходом его сравнить символы со вторым словом. Но программировать это для меня еще через чур сложно
Сложное решение, будет затруднительно разобраться с повторяющимися элементами.
Вот если обе строки распарсить... Но тогда от сортировки это будет отличаться только более сложным алгоритмом.
akk
 Аватар для akk
44 / 44 / 7
Регистрация: 28.01.2012
Сообщений: 341
18.02.2013, 17:03     Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми? #5
Цитата Сообщение от lemegeton Посмотреть сообщение
будет затруднительно разобраться с повторяющимися элементами
а по-моему это тут не важно, главное чтобы
Цитата Сообщение от Zyfchik Посмотреть сообщение
можно переставить буквы в одном из слов, чтобы слова стали одинаковыми
если надо, и подойдет такой вариант, то могу кинуть код обходов бинарных деревьев. только он на Си, а не на Си++
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
18.02.2013, 17:07     Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми? #6
Цитата Сообщение от akk Посмотреть сообщение
а по-моему это тут не важно, главное чтобы
Прикиньте, как будут разбираться строки aaaab и bbbba. Обход должен учитывать повторения, причем как в разобранной строке, так и в не разобранной.
akk
 Аватар для akk
44 / 44 / 7
Регистрация: 28.01.2012
Сообщений: 341
18.02.2013, 17:18     Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми? #7
Цитата Сообщение от lemegeton Посмотреть сообщение
Прикиньте, как будут разбираться строки aaaab и bbbba.
Так вроде в структуре дерева есть еще переменная count (счетчик)
C++
1
2
3
4
5
6
struct tnode {
    char * word;
    int count;
    struct tnode *left;
    struct tnode *right;
};
в 1 случаи
а count = 4
b count = 1
во 2
а count = 1
b count = 4
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
23.02.2013, 09:13     Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми? #8
Хм. Неплохая идея. Тогда можно упростить и не городить дерево, воспользоваться массивом и посчитать количество символов в строках.

Добавлено через 20 часов 7 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cstring>
 
bool isAnagram(const char *a, const char *b) {
  const int numberOfCharacters = 256;
  if (strlen(a) != strlen(b)) {
    return false;
  }
 
  int count[numberOfCharacters];
  for (int i = 0; i < numberOfCharacters; ++i) {
    count[i] = 0;
  }
 
  while (*a != '\0' || *b != '\0') {
    ++count[*a++];
    --count[*b++];
  }
 
  for (int i = 0; i < numberOfCharacters; ++i) {
    if (count[i] != 0) {
      return false;
    }
  }
 
  return true;
}
 
int main(int argc, char **argv) {
  std::cout << ((isAnagram("aabbb", "bcabb")) ? "yes" : "no") << std::endl;
  std::cout << ((isAnagram("acbbb", "bcabb")) ? "yes" : "no") << std::endl;
 
  std::cin.get();
  return 0;
}
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
23.02.2013, 10:25     Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми? #9
C++
1
2
3
4
5
6
7
8
9
 using std::string;
bool isAnagram(const string& word1, const string& word2)
{
    string w1(word1);
    std::sort(w1.begin(), w1.end());
    string w2(word2);
    std::sort(w2.begin(), w2.end());
    return w1 == w2;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.02.2013, 12:23     Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми?
Еще ссылки по теме:

C++ Заданы две символьные строки. Все ли буквы первого слова встречаются во втором
C++ Даны два слова. Напечатать только те буквы слов, которые есть только в одном из них
Заданы две строки одинаковой длины. Построить новую строку, состоящую из символов как одной, так и другой C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
23.02.2013, 12:23     Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми? #10
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <string>
#include <algorithm>
 
bool compare(const std::string& s1, const std::string& s2)
{
    if (s1.size() != s2.size()) return false;
    std::string comp(s1);
    std::sort(comp.begin(), comp.end());
    do
    {
        if (comp == s2)
            return true;
    }while (std::next_permutation(comp.begin(), comp.end()));
    return false;
}
 
int main() 
{
    std::string first = "discovery";
    std::string second = "diveryocs";
    std::string third = "discovero";
    
    std::cout << std::boolalpha;
    std::cout<<first<<" and "<<second<<" : "<<compare(first, second)<<"\n";
    std::cout<<first<<" and "<<third<<" : "<<compare(first, third)<<"\n";
    return 0;
}
Yandex
Объявления
23.02.2013, 12:23     Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми?
Ответ Создать тему
Опции темы

Текущее время: 05:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru