Есть несколько строк со словами (комбинациями символов), разделенными разделителями.

Пример:
a:b:c:d
b:e:f
g:h
i:j
g:k:
z:w:f

Подскажите, как оптимальным образом получить из этого независимые цепочки слов (напр., это синонимы, и нужно получить независимые цепочки синонимов), т.е. такие, про которые известно, что данные слова не встречаются в других цепочках.
В данном случае мы должны получить:

a:b:c:d:e:f:w:z
g:h:k
i:j

Желательно без рекурсий.

как-то путано написали

вам попросту нужно объединить слова имеющие одинаковые буквы

берете исходное слово, каждую его букву ищите в результирующих словах
если нашли, то объединяете такие результирующие слова в одно и добавляете буквы исходного слова
если не нашли, то к результирующим словам добавляете новое слово из букв исходного
выполняем тоже самое со следующим исходным словом

как видите, рекурсии не наблюдается

Поясню еще. Здесь под буквами имелись в виду некоторые слова различные, просто для сокращения записи написал.
Вот еще пример:
есть синонимы (степень "схожести" условная):

автомобиль:машина:тачка
тачка:самодвижущийся экипаж
трамвай:рельсовый транспорт
кэб:повозка
повозка:карета
метро:подземка

Нужно объединить в строки независимые цепочки синонимов, то есть чтобы каждое слово в ней являлось синонимом других и не являлось синонимом для остальных слов из др. цепочек.
В данном случае получим:

автомобиль:машина:тачка:самодвижущийся экипаж
трамвай:рельсовый транспорт
кэб:повозка:карета
метро:подземка


Так вот, как это сделать оптимально?

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

сказанное мной ранее остается в силе и в этом случае