4 / 4 / 0
Регистрация: 26.06.2016
Сообщений: 115
1

Сравнить буквы одного слова с другом слове

08.05.2018, 23:01. Показов 7168. Ответов 29
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте,есть такая задача. Надо сравнить буквы одного слова в другом слове и вывести true если они равны. Т.е. например есть слово
- опт
и слово
- пот
По сути они разные слова,но буквами они совпадают, т.е. выведется true.
Но проблема в том что решение в лоб не подходит, сделать 2 цикла и перебирать просто все символы, т.к. сложность такого метода будет O(n2) а надо или O(n) или O(logn*n). Тема на которой мне задали этот вопрос была по коллекция, пот я бьюсь и все никак не могу решить. Прошу кто может то помогите,заранее спасибо.
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.05.2018, 23:01
Ответы с готовыми решениями:

Вычеркните из одного слова все буквы, встречающиеся в другом слове.
Вычеркните из одного слова все буквы, встречающиеся в другом слове.

Удалить из слова все буквы, которые встречаются в другом слове
Напишите программу, удаляющую из любого слова все буквы, которые встречаются в другом слове

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

Как прочитать текст из одного файла и сравнить с текстом в другом файле
Здравствуйте уважаемые форумчане. Помогите пожалуйста как прочитать текст из одного файла и...

29
Эксперт Java
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
08.05.2018, 23:47 2
держи, потестируй как следует
Java
1
2
3
4
5
6
7
8
public static boolean isAnagram(String s1, String s2) {
        int alphabetLength = 'z' - 'a' + 1;
        int[] letterCounter = new int[alphabetLength];
        Function<String, IntStream> prepareString = s -> s.toLowerCase().replaceAll("[^a-z]", "").chars().map(c -> c - 'a');
        prepareString.apply(s1).forEach(c -> letterCounter[c]++);
        prepareString.apply(s2).forEach(c -> letterCounter[c]--);
        return Arrays.stream(letterCounter).allMatch(i -> i == 0);
    }
1
Am I evil? Yes, I am!
Эксперт PythonЭксперт Java
17554 / 10311 / 2819
Регистрация: 21.10.2017
Сообщений: 22,367
08.05.2018, 23:57 3

Java
1
2
3
4
5
6
7
private boolean test(String s1, String s2){
        char[] s11 = s1.toCharArray();
        char[] s12 = s2.toCharArray();
        Arrays.sort(s11);
        Arrays.sort(s12);
        return Arrays.toString(s11).equals(Arrays.toString(s12));
    }
0
185 / 155 / 88
Регистрация: 04.10.2014
Сообщений: 397
09.05.2018, 00:01 4

Java
1
2
3
public static boolean isStringsLettersEquals(String str1, String str2){
        return Arrays.equals(str1.chars().sorted().toArray(), str2.chars().sorted().toArray());
    }
0
Эксперт Java
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
09.05.2018, 00:05 5
про сложность то для кого написано?

Добавлено через 2 минуты
Цитата Сообщение от xoraxax Посмотреть сообщение
Function<String, IntStream> prepareString = s -> s.toLowerCase().replaceAll("[^a-z]", "").chars().map(c -> c - 'a');
вот это кстати неплохо бы разделить на две функции. И после первой сравнить длину строк.
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!
Эксперт PythonЭксперт Java
17554 / 10311 / 2819
Регистрация: 21.10.2017
Сообщений: 22,367
09.05.2018, 09:05 7
АнатолийШ, можно вместо массива положить в коллекцию символы, отсортировать и сравнить. И "доставать" ничего не надо
0
Эксперт Java
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)
Java
1
2
3
4
5
6
7
8
9
    public static boolean isAnagram(String s1, String s2) {
        for (Integer i : new HashMap<Integer,Integer>(){
            {
                for (int s : s1.toCharArray()) put(s, getOrDefault(s, 0) + 1);
                for (int s : s2.toCharArray()) put(s, getOrDefault(s, 0) - 1);
            }
        }.values()) if (i != 0) return false;
        return true;
    }
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
Эксперт Java
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
Эксперт Java
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
09.05.2018, 21:35 20
Цитата Сообщение от АнатолийШ Посмотреть сообщение
Вроде бы задаю адекватные вопросы
вроде бы нет, учитывая, что весь алгоритм разжеван, надо просто сесть и написать пару циклов
0
09.05.2018, 21:35
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.05.2018, 21:35
Помогаю со студенческими работами здесь

Как найти буквы которые есть в одном слове, но нет в другом
Есть два слова, слова похожи, но отличаются несколькими буквами, как найти эти буквы?

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

Вычеркнуть из слова X те буквы которые встречаются в слове Z
Вычеркнуть из слова X те буквы которые встречаются в слове Z

Вычеркнуть из слова Х те буквы, которые встречаются в слове Z
var x: String; y: String; a,i,k,j:Integer; begin readln(x); readln(y); ...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru