用于检查字符串是否是从子字符串列表构建的算法

Question

给你一个字符串和一个字符串数组.如何快速检查,如果这个字符串可以通过连接数组中的一些字符串来构建？

这是一个理论问题,出于实际原因我不需要它.但我想知道,如果有一些好的算法.

编辑 阅读一些我已经注意到的答案,这可能是NP-Complete问题.即使找到字符串的子集,它们将具有相同的长度,作为给定的字符串也是经典的子集求和问题.

所以我想这没有简单的答案.

编辑

现在看来,它毕竟不是NP-Complete问题.那更酷:-)

编辑

我想出了一个通过一些测试的解决方案:

def can_build_from_substrings(string, substrings):
    prefixes = [True] + [False] * (len(string) - 1)
    while True:
        old = list(prefixes)
        for s in substrings:
            for index, is_set in enumerate(prefixes):
                if is_set and string[index:].startswith(s):
                    if string[index:] == s:
                        return True
                    prefixes[index + len(s)] = True
        if old == prefixes: # nothing has changed in this iteration
            return False

我相信时间是O(n * m^3),n长度substrings和m长度在哪里string.你怎么看？

Answer 1

注意:我假设您可以多次使用每个子字符串.您可以通过更改我们定义子问题的方式来概括解决方案以包含此限制.这将对空间以及预期的运行时间产生负面影响,但问题仍然是多项式的.

这是一个动态编程问题.(还有一个很棒的问题!)

composable(S, W)如果S可以使用子串列表写入字符串,则将其定义为true W.

S 当且仅当:

1. S开始于一个子w在W.
2. 在剩余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)空间进行记忆.

(注意,如果写入伪代码使用O(n ^ 2)空间,但散列记忆键会减轻这一点.)

编辑

这是一个有效的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