Примечание: здесь я предполагаю, что вы можете использовать каждую подстроку более одного раза. Вы можете обобщить решение, включив это ограничение, изменив способ определения подзадач. Это окажет негативное влияние на пространство, а также на ожидаемое время выполнения, но проблема остается полиномиальной.
Это проблема динамического программирования. (И отличный вопрос!)
Давайте определим composable(S, W) как истинное, если строка S может быть записана с использованием списка подстрок W.
S компонуется тогда и только тогда, когда:
S начинается с подстроки w в W. - Остальная часть
S после w также может быть составной.
Давайте напишем какой-нибудь псевдокод:
COMPOSABLE(S, W):
return TRUE if S = "" # Base case
return memo[S] if memo[S]
memo[S] = false
for w in W:
length <- LENGTH(w)
start <- S[1..length]
rest <- S[length+1..-1]
if start = w AND COMPOSABLE(rest, W) :
memo[S] = true # Memoize
return memo[S]
Этот алгоритм имеет O (m * n) время выполнения, предполагая, что длина подстрок не является линейной w / r / t для самой строки, и в этом случае время выполнения будет O (m * n ^ 2) (где m это размер списка подстрок, а n это длина рассматриваемой строки). Для запоминания используется пространство O (n).
(N.B. Как написано, псевдокод использует O (n ^ 2) пробел, но хеширование ключей памятки уменьшило бы это.)
EDIT
Вот рабочая реализация Ruby:
def composable(str, words)
composable_aux(str, words, {})
end
def composable_aux(str, words, memo)
return true if str == "" # The base case
return memo[str] unless memo[str].nil? # Return the answer if we already know it
memo[str] = false # Assume the answer is `false`
words.each do |word| # For each word in the list:
length = word.length
start = str[0..length-1]
rest = str[length..-1]
# If the test string starts with this word,
# and the remaining part of the test string
# is also composable, the answer is true.
if start == word and composable_aux(rest, words, memo)
memo[str] = true # Mark the answer as true
end
end
memo[str] # Return the answer
end