Word Break — разбиение строки на слова

Задача стоит следующим образом: Дана строка и словарь, возможно ли разбить данную строку на слова из словаря?

Например, при входных данных:

String s = "cчастливтотктосчастливусебядома";
String[] dictionary = new String[] { "счастлив", "тот", "кто", "у", "себя", "дома" };

возвратит true, т.к. строку можно разбить "cчастлив"+"тот"+"кто"+"счастлив"+"у"+"себя"+"дома";

Обдумав проблему, можно понять, что теоретически возможен более чем один вариант разбиения. При этом не каждое разбиение является удачным. Таким образом, если мы добавим в словарь слова "себ" и "яд", то у нас будет два варианта:

"cчастлив"+"тот"+"кто"+"счастлив"+"у"+"себя"+"дома" - удачное разбиение.

"cчастлив"+"тот"+"кто"+"счастлив"+"у"+"себ" + "яд" ["ома"] - неудачное разбиение, т.к. слово "ома" отсутствует в словаре, а также невозможно составить из других слов словаря.

Поскольку существет другой способ разбить эту строку на слова из словаря, неудачное разбиение следует проигнорировать.

Разберем решение этой задачи алгоритмом, предложенным на leetcode.

Суть алгоритма в следующем: создадим массив булевых значений, каждый элемент которого будет обозначать, является ли данная позиция концом слова в нашей строке. Начнем цикл, в котором вначале выясним все окончания слов, начинающихся с первой позиции. Затем повторим процесс для каждой вновь найденной позиции. Если позиция не была помечена ранее как конец слова, просто проигнорируем ее, т.к. если до нее нельзя добраться через последовательность слов, анализировать ее на начало следующего слова бессмысленно.

Таким образом, мы пройдем через все последовательности слов в нашей строке, которые начинаются с позиции 0. Если после прохождения по всем позициям последний бит нашего массива окажется установлен, искомая последовательность слов существует.

Рассмотрим работу этого алгоритма на приведенных выше данных:

"cчастливтотктосчастливусебядома"
[0000000100000000000000000000000]

"cчастливтотктосчастливусебядома"
[0000000100100000000000000000000]

"cчастливтотктосчастливусебядома"
[0000000100100100000000000000000]

"cчастливтотктосчастливусебядома"
[0000000100100100000001000000000]

"cчастливтотктосчастливусебядома"
[0000000100100100000001100000000]

"cчастливтотктосчастливусебядома" "cчастливтотктосчастливусебядома"
[0000000100100100000001100100000] [0000000100100100000001100110000]

"cчастливтотктосчастливусебядома"
[0000000100100100000001100111000]

"cчастливтотктосчастливусебядома"
[0000000100100100000001100011001]

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

Моя имплементация решения
https://gist.github.com/codekrolik/b2e4251b2668c6a3ab14

Тесты
https://gist.github.com/codekrolik/8e1e9ad252d1b33f69fb

Тематический пост на leetcode.