4 / 4 / 0
Регистрация: 26.06.2016
Сообщений: 115
|
|
1 | |
Сравнить буквы одного слова с другом слове08.05.2018, 23:01. Показов 7168. Ответов 29
Метки нет (Все метки)
Здравствуйте,есть такая задача. Надо сравнить буквы одного слова в другом слове и вывести true если они равны. Т.е. например есть слово
- опт и слово - пот По сути они разные слова,но буквами они совпадают, т.е. выведется true. Но проблема в том что решение в лоб не подходит, сделать 2 цикла и перебирать просто все символы, т.к. сложность такого метода будет O(n2) а надо или O(n) или O(logn*n). Тема на которой мне задали этот вопрос была по коллекция, пот я бьюсь и все никак не могу решить. Прошу кто может то помогите,заранее спасибо.
1
|
08.05.2018, 23:01 | |
Ответы с готовыми решениями:
29
Вычеркните из одного слова все буквы, встречающиеся в другом слове. Удалить из слова все буквы, которые встречаются в другом слове Даны два слова. Вычеркнуть из первого слова те буквы,которые встречаются во втором слове Как прочитать текст из одного файла и сравнить с текстом в другом файле |
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
||||||
08.05.2018, 23:47 | 2 | |||||
держи, потестируй как следует
1
|
Am I evil? Yes, I am!
17554 / 10311 / 2819
Регистрация: 21.10.2017
Сообщений: 22,367
|
||||||
08.05.2018, 23:57 | 3 | |||||
0
|
185 / 155 / 88
Регистрация: 04.10.2014
Сообщений: 397
|
||||||
09.05.2018, 00:01 | 4 | |||||
0
|
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
|
09.05.2018, 00:05 | 5 |
про сложность то для кого написано?
Добавлено через 2 минуты вот это кстати неплохо бы разделить на две функции. И после первой сравнить длину строк.
0
|
4 / 4 / 0
Регистрация: 26.06.2016
Сообщений: 115
|
|
09.05.2018, 08:08 [ТС] | 6 |
Спасибо за ваш ответ.Это понял,но если учесть еще тот факт что например мне нельзя пользоваться stream, т.к. его еще по сути я не проходил и не должен знать,то каким образом можно реализовать с необходимой мне сложностью.
Просто я думал засунуть в какую то коллекцию, а потом доставать из нее сравнивать, но это все равно будет сложность n2. Не понимаю как добиться того что мне надо,без stream, все равно. Добавлено через 10 минут Только еще момент, что у меня не аннаграмма ,у меня просто 2 слова в которых надо проверить наличие одних и тех же букв. Не важно путь будет слово опять же - о п т и - т о п И там и там те же буквы, значит нам подходит.
0
|
Am I evil? Yes, I am!
17554 / 10311 / 2819
Регистрация: 21.10.2017
Сообщений: 22,367
|
|
09.05.2018, 09:05 | 7 |
АнатолийШ, можно вместо массива положить в коллекцию символы, отсортировать и сравнить. И "доставать" ничего не надо
0
|
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
|
09.05.2018, 09:14 | 8 |
АнатолийШ, надо понять, что делает мой код, и сделать то же без стримов. И что такое по-твоему анаграмма?
0
|
494 / 340 / 134
Регистрация: 14.06.2016
Сообщений: 658
|
||||||
09.05.2018, 11:50 | 9 | |||||
Собирай в HashMap тогда, если принципиально, там поиск О(1)
0
|
4 / 4 / 0
Регистрация: 26.06.2016
Сообщений: 115
|
|
09.05.2018, 12:40 [ТС] | 10 |
iSmokeJC, я так думал что закинуть в HashMap символы уже,но вот вопрос сама операция когда я добавляю в HashMap будет O(1) но то что я буду добавлять n элементов то вся операция будет равна o(n) а нам еще надо в цикле сравнить значения, по сути опять же будет O(n2) или я не прав ? Или я не так вас понял?
xoraxax, анаграмма это слово которое пишется и читается одинаково как с начала так и с конца. Честно говоря в стримах я не очень,может код и пойму но переложить именно на коллекции с нужной мне сложностью боюсь что не смогу.Не могли бы вы натолкнуть на мысль что именно надо сделать? vcrop, ваш код как я понял проверяет именно аннаграмму,а мне необходимо другое. Чтобы просто набор букв в обоих словах был одним и тем же, например опт и топ Поэтому тут неправильно для меня, или я не так понял ваш код.
0
|
2677 / 1995 / 496
Регистрация: 17.02.2014
Сообщений: 9,357
|
|
09.05.2018, 15:17 | 11 |
как я понимаю, добавление в HashMap O(n), поиск O(1), общая сложность не превосходит желаемой.
0
|
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
|
09.05.2018, 15:23 | 12 |
https://ru.wikipedia.org/wiki/... 0%BC%D0%B0
создаем массив из 26 элементов (по количеству букв), из строк убираем все, кроме букв, приводим в lowerCase, проверяем, что длины строк равны, проходим по первой строке, для каждой буквы увеличивая значение в соответствующей ячейке в массиве, проходим так же по второй строке, но в этой раз уменьшаем значения в массиве. Если строки являются анаграммами, т.е. состоят из одинаковых наборов букв, тогда все значения в нашем массиве будут равны 0. Вроде все просто.
0
|
4 / 4 / 0
Регистрация: 26.06.2016
Сообщений: 115
|
|
09.05.2018, 19:30 [ТС] | 13 |
Aviz__, добавление o(n) достать o(1), но есть же вторая строка которая также в цикле до n говорит что конкретно достать и того получается o(n2)
xoraxax,Но если у нас одна и та же буква повторяется, то тогда не работает так как вы сделали? А если просто завести переменную и в цикле добавлять значения char приводя их к int как и вы делали с одного слова ,а со второго отнимать, и потом сравнить эту переменную с нулем то будет ли это правильно?
0
|
2677 / 1995 / 496
Регистрация: 17.02.2014
Сообщений: 9,357
|
|
09.05.2018, 19:41 | 14 |
одну добавили o(n), со второй, когда берете для поиска, опять o(n), сам поиск o(1).
0
|
4 / 4 / 0
Регистрация: 26.06.2016
Сообщений: 115
|
|
09.05.2018, 19:45 [ТС] | 15 |
Aviz___, Ну как я и сказал общая сложность то o(n2), а мне надо o(n)
0
|
2677 / 1995 / 496
Регистрация: 17.02.2014
Сообщений: 9,357
|
|
09.05.2018, 19:47 | 16 |
если два перебора подряд, не вложены друг в друга, то o(n).
0
|
4 / 4 / 0
Регистрация: 26.06.2016
Сообщений: 115
|
|
09.05.2018, 19:53 [ТС] | 17 |
Т.е. 1) я добавляю все char в HashMap
2) в цикле я беру char из второго слова и удаляю этот элемент из HashMap 3)если HashMap пуста то все верно если нет то не верно.
0
|
xoraxax
|
09.05.2018, 21:21
#18
|
Не по теме: АнатолийШ, ощущение такое, что ты ваще не понимаешь, о чем говоришь
0
|
4 / 4 / 0
Регистрация: 26.06.2016
Сообщений: 115
|
|
09.05.2018, 21:26 [ТС] | 19 |
xoraxax, в чем это проявляется?Что именно вас наводит на эту мысль?Вроде бы задаю адекватные вопросы.
0
|
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
|
09.05.2018, 21:35 | 20 |
вроде бы нет, учитывая, что весь алгоритм разжеван, надо просто сесть и написать пару циклов
0
|
09.05.2018, 21:35 | |
09.05.2018, 21:35 | |
Помогаю со студенческими работами здесь
20
Как найти буквы которые есть в одном слове, но нет в другом Для заданного достаточно длинного слова найти в имеющемся тексте все слова, в которых использованы только буквы, имеющиеся в заданном слове Вычеркнуть из слова X те буквы которые встречаются в слове Z Вычеркнуть из слова Х те буквы, которые встречаются в слове Z Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |