Используя пары слов из словаря, не содержащие общих букв, найдите пару, которая максимизирует сумму длин слов.

Вы можете сделать это за O(N^2 * 26) (26 представляет собой количество символов в вашем словаре, вероятно, английский алфавит).

ПЕРВЫЙ Создайте массив 2D bool, D[i][j].

я - целое число

j - символ от 'a' до 'z' (вы можете использовать код ASCII вместо символа)

D[i][j] = 1, если слово с индексом i содержит букву j, иначе D[i][j] = 0;

После того, как у вас есть этот 2D-массив, вы можете проверить каждую пару слов, если у них есть общая буква (вы выполняете итерацию для каждой пары, каждой буквы вашего словаря). Если они этого не сделают, вы реализуете максимальную сумму.

Вот подход, который можно было бы назвать O(n*avg), хотя, возможно, его следовало бы назвать O(n*avg+a*2^a), где a — размер алфавита, n — количество слов, а avg — средняя длина слов в словаре, на случай, если вы сделайте это с большими алфавитами. Это не будет улучшением по сравнению с методом грубой силы, упомянутым Богданом Попом, если ваш словарь содержит всего несколько тысяч слов, но это будет улучшение, если словарь содержит сотни тысяч слов. Для сравнения, словарь SOWPODS, используемый некоторыми игроками в Scrabble, содержит более 267 000 слов. Большая часть этого подхода, до последнего абзаца, по существу такая же, как Ответ Михала Форишека на Quora.

Для каждого слова w определить его длину l(w) и какие буквы оно содержит s(w).

Для каждого из 2 ^ a подмножеств алфавита определите самое длинное слово, содержащее именно эти буквы, перебирая каждое слово w и заменяя сохраненную длину в s (w) максимальным значением самого себя и l (w).

Для каждого из 2^a подмножеств алфавита определите самое длинное слово, содержащее не более этих букв. Это можно сделать за O(a*2^a) шагов, потому что каждое подмножество размера k покрывает k меньших подмножеств с k-1 буквами. Мы вычисляем значение индуктивно как самое длинное слово, содержащее именно эти буквы или содержащееся в одном из k-1 покрытых подмножеств.

Теперь мы можем перебрать все подмножества алфавита, суммируя длину самого длинного слова, используя именно эти буквы, и длину самого длинного слова, содержащегося в дополнении этого подмножества.

Одна неудовлетворительная часть этого подхода заключается в том, что время значительно увеличивается из-за включения необычных букв. Затрачиваемое время увеличивается примерно в 20 раз из-за Q, X, J и Z, которые не так уж часто встречаются в словах в целом, и я думаю, что не в длинных словах. Итак, предположим, что есть r слов, содержащих хотя бы одну из b редких букв. Мы можем использовать описанный выше алгоритм для слов без редких букв за O(n*avg+(a-b)2^(a-b)) шагов. Затем мы можем подобрать пары слов, которые оба содержат редкие буквы, за O(r^2*a) шагов. Наконец, мы можем проверить наличие пар слов, в которых первое содержит редкую букву, а второе нет, перебирая r слов, содержащих редкую букву, и проверяя самое длинное слово, содержащее в дополнении только обычные буквы. В последнем случае требуется O(r*avg) шагов, поэтому асимптотически им можно пренебречь. Итак, выбрав несколько редких букв, мы можем сократить время до O(n*avg+(a-b)2^(a-b)+r^2*avg). По крайней мере, в стандартном английском словаре есть редко используемые буквы, так что это было бы сокращением.