Algorithm for checking if a string was built from a list of substrings

Question

You are given a string and an array of strings. How to quickly check, if this string can be built by concatenating some of the strings in the array?

This is a theoretical question, I don't need it for practical reasons. But I would like to know, if there is some good algorithm for this.

EDIT Reading some answer I have noticed, that this is probably NP-Complete problem. Even finding a subset of strings, that will together have same length, as a given string is a classic subset sum problem.

So I guess there is no easy answer to this.

EDIT

Now it seems, that it is not a NP-Complete problem after all. That's way cooler :-)

EDIT

I have came up with a solution that passes some tests:

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

I believe the time is O(n * m^3), where n is length of substrings and m is length of string. What do you think?

Answer 1

What about this?

substrings = ["a", "bb", "c"]

def checkString(string):
    for substring in substrings:
        if substring in string:
            string = string.replace(substring, "")
    if string == "":
        return True
    else:
        print(string)
        return False

It esentially just goes through all the allowed substrings and if they're present in the string it removes them and then checks if the resulting string is "".

Answer 2

I have come up with a one liner for this using dynamic programming principles. The function foo takes a string and a list of substrings to decide if it's possible to construct the given string from the given list

foo = lambda s, arr:  not s or any(foo(s[len(n):], arr) for n in arr if s[:len(n)]==n)

The one liner broken down for readability:

def foo(s, arr):
if not s: return True
for sub in arr:
    if s[:len(sub)] == sub:
        if foo(s[len(sub):], arr):
            return True
return False

Answer 3

Note: I assume here that you can use each substring more than once. You can generalize the solution to include this restriction by changing how we define subproblems. That will have a negative impact on space as well as expected runtime, but the problem remains polynomial.

This is a dynamic programming problem. (And a great question!)

Let's define composable(S, W) to be true if the string S can be written using the list of substrings W.

S is composable if and only if:

1. S starts with a substring w in W.
2. The remainder of S after w is also composable.

Let's write some pseudocode:

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]

This algorithm has O(m*n) runtime, assuming the length of the substrings is not linear w/r/t to the string itself, in which case runtime would be O(m*n^2) (where m is the size of the substring list and n is the length of the string in question). It uses O(n) space for memoization.

(N.B. as written the pseudocode uses O(n^2) space, but hashing the memoization keys would alleviate this.)

EDIT

Here is a working Ruby implementation:

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

Answer 4

What you are looking for is a parser. A parser will check whether a certain word belongs to a certain language. I am not sure of the exact computattional complexity of your problem. Some of the above seems to be correct (there is no need at all for exhaustive search). One thing for sure, it s not NP-Complete.

The alphabet of your language would be all the small substrings. The word you are looking for is the string you have. A regular expression can be a simple Kleene star, or a a very simply context free grammar that is nothing but Or's.

The main issue in the algorithm is: what if the some of the substrings are actually substrings to other substrings ... that is, what if we have substrings: "ab", "abc", "abcd", ... , In this case, the order of checking the substrings will change the complexity. For this, we have LR-parsers. I guess they are the best in solving such problems.

I will find you the exact solution soon.

Answer 5

If each substring must be used only once but not all of them must be used...

For each permutation of size N from the substrings that is equal in size to the original string check it, if none, do a permutation of N+1 items, end so forth, until you exhaust all the permutations.

Of course NP complete, slow as hell, but i think that no normal solutions exist.

To explain why the solutions where removing substrings from the original string won't ever work:

Have a string "1234123" and array "12","34","123". If you remove "123" from the start, you have a false negative. A similar example where removing from the end would be: "1234123" : "23,"41","123".

With backtracking with greedy: (m string length 7, n num elements 3) - take the longest: 123 - remove it from first occurence O(3) - try other two with the rest: no go + O((n-1)*(m-3)) - backtrack O(1) - remove from second: O(m-3) - try other two O((n-1)*m-3) = O(30)

Permutations of 1 + 2 + 3 = O(3) + O(4) + O(6) = O(13). So for small subset lenght permutations are actually faster than backtracking. This will change if you ask for a lot of substrings to find (in most cases but not all).

You can remove only the nonexisting substrings from the array to lower the number of permutations from n^n to n^(n-1) for each removed nonexisting substring.

Answer 6

Let me suggest using Suffix Trees (using Ukkonen's online algorithm to build it) which seems to be suitable in terms of searching common substrings in two texts. You could find more information in wikipedia/special sources. The task is

Find all z occurrences of the patterns P1..Pn of total length m
enter code hereas substrings in O(m + z) time.

so you see there exists very cool solution. Hope this will work for you. This is actually more suitable for repeating scans, rather than a single scan.

Answer 7

Inspired by @cnicutars answer:

• function Possible(array A, string s)
  • If s is empty, return true.
  • compute the array P of all strings in A that are a prefix of s.
  • If P is empty, return false.
  • for each string p in P:
    • if Possible(A with p removed, s with prefix p removed) return true
  • return false

Answer 8

It's definitely not quick but you here's an idea:

• Iterate over all the strings, checking if the target string "begins" with any of them
• Take the longest string with which the target string begins, remove it from the list and trim it from the main string
• Rinse, repeat

Stop when you're left with a 0 length target string.

As I said before, this is definitely not fast but should give you a baseline ("it shouldn't get much worse than this").

EDIT

As pointed out in the comments, this will not work. You will have to store the partial matches and fall back on them when you find there is no way further.

• When you find that a string is the head of the target, push it onto a list. After building the list, you will naturally try the biggest "head" of the target
• When you find that the head you tried doesn't fit with what's left, try the next best head

This way, eventually you'll explore the entire space of solutions. For every candidate head you'll try every possible tail.

Answer 9

Here is a rough idea that should work.

1. Copy the source string into a new string
2. While the copy string still has data and there are still substrings a. Grab a sub string, if copy.contains(substr) copy.remove(substr)
3. If the copy is now empty then yes, you could construct the string
4. If copy is not empty, throw out the first substr that was removed from the string and repeat.
5. If all substrings are gone and copy is still not empty then no, you can't construct it.

Edit: A way to possibly improve this would be to first iterate all of the substrings and throw out any that are not contained in the main string. Then go through the above steps.

Answer 10

It seems to me a problem can be solved by simple linearly traversing of array and comparison. However there could be multiple pass. You can devise a strategy to minimize the passes. For example constructing a sub array of all the substrings of the original string in first pass. Then try out different variations linearly.

Answer 11

two options sprint to mind but neither of them seem very elegant.

1) brute force: do it like you would a password generator i.e. word1+word1+word1 > word1+word1+word2 > word1+word1+word3 etc etc etc

the trick there is the length so youd have to try all combinations of 2 or more words and you don't know where to set the limit. Very time consuming.

2) take the string in question and run a find in on it for every word you have 1 at a time. maybe check the length and if its greater than 0 do it again. keep doing it till you hit zero it cant find any more results. if you hit 0 its a win if not its a lose. I think this method would be a lot better than the first but I imagine someone will have a better suggestion.

Answer 12

This is how I would do it.

1. Determine the length of the target string.
2. Determine the length of each string in the substring array
3. Determine which combination of substrings would yield a string with the same length as the target string (If any, if not you're done)
4. Generate all permutations of the substring combinations determined in step 3. Check if any of them match the target string.

Generating all permutations is a processor heavy task, so if you can cut down on your 'n' (input size), you'll gain some considerable efficiency.