singlepost

Анаграммы << На главную или назад  

Даны 2 строки S и W, составленныеиз прописных латинских букв. Составить программу, проверяющую, можно ли из букв, входящих в S, составить W. Каждую букву S можно использовать только один раз.

Косяк в том что не знаю как сделать чтоб буквы не повторялись
ТАК В БОШКЕ ЕСТЬ ИДЕЯ НО я ненавижу цыкл while

59 ответов в теме “Анаграммы”

  1. 11
    Кирилл Быков ответил:

    Завести массив 256 элементов (index=char) для W и S, занулить его, подсчитать в соответствующем элементе количество символов с кодом=индекс элемента, и смотреть, как бы в массиве для W соответствующие элементы не превысили соответствующие для S. Условие выполнено если — то W из S составить можно.

  2. 10
    Дмитрий Потапов ответил:

    отсортировать и проверить что W\S!=0

    итого два вызова std::sort и один вызов std::set_difference – сложность O(n*log n)

    если std::sort заменить арифметической сортировкой – сложность O(n)

  3. 9
    Алексей Федоров ответил:

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

  4. 8
    Леонид Максимов ответил:

    по мне тоже проще посчитать все символы. как-нибудь так (не пинать, если ошибки есть. я уже года три не трогал этот язык):
    int cnt[26];
    for(char *p = s; *p; cnt[*p++ - 'A']++);
    for(char *p = w; *p; cnt[*p++ - 'A']–);
    for(int i=0; i < 26; i++) if cnt[i] < 0 break;
    return i != 26;
    возвращает 0, если можно составить W из букв из S.

  5. 7
    Петр Полежаев ответил:

    Можно проще.

    пусть s_cnt[i] – количество вхождений символа с номером i в S (0<=i<=25).
    w_cnt[i] – количество вхождения символа с кодом i в W.

    W может быть составлена из символов S с учетом числа вхождений каждого символа <=> для всех i=0..25s_cnt[i] >= w_cnt[i].

    Вычисление s_cnt:
    1. s_cnt[i] = 0 для всех i=0..25
    2. для всех символов строки S (j = 0…m-1)
    s_cnt[S[j] -'A']++;

    Вычисление w_cnt аналогично.

  6. 6
    Костя Мичурин ответил:

    а как узнать что она цыфра может лучше вообще знак удалить :)

  7. 5
    Алексей Руденко ответил:

    можно и удалить

  8. 4
    Алексей Руденко ответил:

    w[1] = q
    s[1]=w[1]
    заменяем s[1] на, допустим, 1
    w="qwer"
    s="1qqq"
    переходим к w[2]=w
    s[1] – цифра, не обрабатываем
    s[2]!=w[2] и s[3]!=w[2] и s[4]!=w[2] значит нельзя собрать

  9. 3
    Алексей Федоров ответил:

    что то простые задачи на ГОС

  10. 2
    Алексей Руденко ответил:

    Может так:
    Читаешь первый символ w, пытаешся найти его в s, если не находишь – значит нельзя составить, если находишь, то заменяешь его, например, на цифру, и так для всех символов w

  11. 1
    Костя Мичурин ответил:

    да но тут косяк есль вот в чем
    w="qwer"
    s="qqqq"
    будет работать правильно
    хотя в принципе можно попробовать :)

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