Вы задали два вопроса:
Можем ли мы считать не-ASCII-символы, используя хеш-таблицу? Ответ: конечно. Когда вы читаете символы (, а не байты ), изучите кодовые точки. Для любой кодовой точки, превышающей 127, поместите ее в хеш-таблицу подсчета. Для символа c добавьте (c, 1), если c нет в таблице, и обновите (c, x) до (c, x + 1), если c уже есть в таблице.
Есть ли лучший способ решить эту проблему, чем ваш подход увеличения счетчиков в a и уменьшения при прохождении через b? Если ваша хеш-таблица дает почти O (1) доступ, то я подозреваю, что нет. Вы смотрите на каждый символ в строке ровно один раз, и для каждого символа вы выполняете либо вставку хеш-таблицы, либо поиск, а также сложение или вычитание и проверку на 0. С несортированными строками у вас есть для в любом случае, посмотрите на все символы в обеих строках, так что вы, я думаю, нашли лучшее решение.
Интервьюер может искать, чтобы вы сказали что-то вроде: «Хммммм, если бы эти строки были действительно массивными файлами, которые не могли поместиться в памяти, что бы я делал?» Или для вас, чтобы спросить: «Ну, строка отсортирована? Потому что, если они, я могу сделать это быстрее ...».
Но теперь давайте скажем, что строки огромные. Единственное, что вы храните в памяти - это хеш-таблица. Unicode имеет только около 1 миллиона кодовых точек, и вы сохраняете целое число для каждой, так что даже если вы получаете данные из файлов размером в гигабайт, вам понадобится всего около 4 МБ или около того для вашей хеш-таблицы (или небольшого кратного этого, так как будет быть над головой).
При отсутствии каких-либо других условий ваш алгоритм хорош. Сортировка строк заранее не годится; он занимает больше памяти и не является линейной операцией.
ДОПОЛНЕНИЕ
Поскольку в ваших первоначальных комментариях упоминался тип char, а не wchar_t, я подумал, что приведу пример использования широких строк. См http://codepad.org/B3MXOgqc
Надеюсь, это поможет.
ADDENDUM 2
Хорошо, вот программа на C, которая показывает, как пройти через широкую строку и работать на уровне персонажа:
http://codepad.org/QVX3QPat
Это очень короткая программа, поэтому я также вставлю ее сюда:
#include <stdio.h>
#include <string.h>
#include <wchar.h>
char *s1 = "abd中日";
wchar_t *s2 = L"abd中日";
int main() {
int i, n;
printf("length of s1 is %d\n", strlen(s1));
printf("length of s2 using wcslen is %d\n", wcslen(s2));
printf("The codepoints of the characters of s2 are\n");
for (i = 0, n = wcslen(s2); i < n; i++) {
printf("%02x\n", s2[i]);
}
return 0;
}
Выход:
length of s1 is 9
length of s2 using wcslen is 5
The codepoints of the characters of s2 are
61
62
64
4e2d
65e5
Чему мы можем научиться из этого? Пара вещей:
- Если вы используете простые старые
char для символов CJK, тогда длина строки будет неправильной .
- Чтобы использовать символы Юникода в C, используйте
wchar_t
- Строковые литералы имеют ведущий
L для широких строк
В этом примере я определил строку с символами CJK и использовал wchar_t и цикл for с wcslen. Обратите внимание, что я работаю с реальными символами, а не с байтами, поэтому я получаю правильное количество символов, равное 5. Теперь я распечатываю каждую кодовую точку. В своем вопросе к собеседованию вы узнаете, является ли кодовая точка >= 128. Я показал их в Hex, как и в культуре, поэтому вы можете найти > 0x7F. : -)
ADDENDUM 3
Несколько заметок в http://tldp.org/HOWTO/Unicode-HOWTO-6.html стоит прочитать. Обработка символов намного больше, чем показывает простой пример, приведенный выше. В комментариях ниже Я. Ф. Себастьян приводит ряд других важных ссылок.
Из немногих вещей, которые необходимо решить, это нормализация. Например, заботится ли ваш интервьюер о том, что, если ему даны две строки, одна из которых содержит только other, а другая C, за которой следует КОМБИНИРОВАННАЯ МАРКА CEDILLA НИЖЕ, они будут одинаковыми? Они представляют один и тот же символ , но один использует одну кодовую точку, а другой - две.