Это сложная задача придумать самый элегантный JavaScript, Ruby или другое решение для относительно тривиальной проблемы.
Эта проблема является более конкретным случаем Самая длинная общая проблема с подстрокой. Мне нужно найти только самую длинную общую начальную подстроку в массиве. Это значительно упрощает проблему.
Например, самая длинная подстрока в [interspecies, interstelar, interstate] является "inters". Однако мне не нужно находить "ific" в [specifics, terrific].
Я решил проблему, быстро скопировав решение в JavaScript в качестве части моего ответа о оболочке, подобной оболочке (тестовая страница здесь). Вот это решение, слегка измененное:
function common_substring(data) {
var i, ch, memo, idx = 0
do {
memo = null
for (i=0; i < data.length; i++) {
ch = data[i].charAt(idx)
if (!ch) break
if (!memo) memo = ch
else if (ch != memo) break
}
} while (i == data.length && idx < data.length && ++idx)
return (data[0] || '').slice(0, idx)
}
Этот код доступен в этом Gist вместе с аналогичным решением в Ruby. Вы можете клонировать суть как репозиторий git, чтобы попробовать:
$ git clone git://gist.github.com/257891.git substring-challenge
Я не очень доволен этими решениями. У меня такое чувство, что они могут быть решены с большей элегантностью и меньшей сложностью исполнения, поэтому я отправляю эту проблему.
Я собираюсь принять в качестве ответа решение, которое я нахожу самым элегантным или лаконичным. Вот, к примеру, сумасшедший рубиновый хак, который я придумал, - определение оператора & на String:
# works with Ruby 1.8.7 and above
class String
def &(other)
difference = other.to_str.each_char.with_index.find { |ch, idx|
self[idx].nil? or ch != self[idx].chr
}
difference ? self[0, difference.last] : self
end
end
class Array
def common_substring
self.inject(nil) { |memo, str| memo.nil? ? str : memo & str }.to_s
end
end
Решения в JavaScript или Ruby предпочтительнее, но вы можете продемонстрировать умное решение на других языках, пока вы объясняете, что происходит. Только код из стандартной библиотеки.
Обновление: мои любимые решения
Я выбрал решение для сортировки JavaScript kennebec как "ответ", потому что он поразил меня как неожиданный, так и гениальный. Если мы проигнорируем сложность фактической сортировки (предположим, что она бесконечно оптимизирована с помощью реализации языка), сложность решения заключается в простом сравнении двух строк.
Другие отличные решения:
- "regex greed" от FM занимает минуту или две, чтобы понять, но тогда изящество этого вас поражает. Yehuda Katz также сделал решение regex, но это более сложный
-
commonprefixв Python - Роберто Бонвалле использовал функцию, предназначенную для обработки путей файловой системы для решения этой проблемы. - Haskell one-liner короток, как если бы он был сжат, и красивый
- простой однострочный Ruby
Спасибо за участие! Как вы можете видеть из комментариев, я многому научился (даже о Ruby).
