1

I need to write a function to detect if a set of strings needs delimiters when concatenated in any order.

For example, the strings ("A","B","C") do not need a delimiter: "ABCBB" -> ["A","B","C","B","B"].

However, the strings ("Pop","corn","Popcorn") do need a delimiter, as the string "Popcorn" is ambiguous: it can either be ["Pop","corn"] or ["Popcorn"].

Two more testcases:

("Pop","Popcorn","Kernel") -> Not ambiguous
("A","AB","BC","BA") -> Ambiguous (on the string "ABCA")

Algorithms that I've considered, but don't work:

  1. Testing if a string starts with another string, which fails ("Pop","Popcorn","Kernel")
  2. Testing if a string is completely made up of other strings, which fails ("A","AB","BC","BA")
  3. Testing all possible combinations of strings (fails to finish on non-ambiguous)

How can I detect (hopefully efficiently) if a set of strings need a delimiter when concatenated?

  • @SilviuBurcea I'm unable to come up with an algorithm that passes all the test cases. – Nathan Merrill Feb 19 '16 at 16:04
  • 1
    This seems off topic. Typically questions about writing or debugging code belong on Stack Overflow. – theMayer Feb 19 '16 at 16:05
  • 3
    @rmayer06 your Help center specifically says "algorithm and data structure concepts" is on topic. I don't need code written for me, I'm asking for an algorithm. – Nathan Merrill Feb 19 '16 at 16:06
  • 2
    This does not appear to be a conceptual question - it seems specific. I would also submit it is unanswerable as-is, because the business rules are not at all clear. – theMayer Feb 19 '16 at 16:10
  • 2
    What seems unclear? The input is a set of strings, and the output returns true if the set of strings can be concatenated in such a way that separating them back out is ambiguous. – Nathan Merrill Feb 19 '16 at 16:14
2

After some thinking, there is a simple algorithm.

Assume you have two strings x and y, and neither is a prefix of the other. Nothing you could append to them would make them equal, so they are of no interest. What you are interested in are strings x and xa, where xa has not been created by adding strings to x: We might be able to add words from your list to both x and xa and get the same two strings. Actually, we are only interested in a.

Let L be your list. We create a set S of all strings a such that for some x, both x and xa can be formed from words in your list, without creating xa by adding words to x. But L contains no prefix of "corn" and no word starting with "corn", so we are finished and L is unambigous.

Initially S is empty. We check all pairs (x, y) of strings in L. If x is empty or x = y then L is ambigous. Otherwise if y = xa or x = ya then add a to the set S. (In your last example, the two strings A and AB in your list add "B" to the set S).

Then for each string x in S, and for each string y in L: If x = y then L is ambiguous. Otherwise if y = xa or x = ya then add a to the set S. Repeat until nothing else can be added to S; in that case L is unambigous.

In your last example, S contains "B". Since L contains "BC" and "BA" we add "C" and "A". "C" doesn't let us anything because no string in L starts with "C". But "A" is actually an element of L, which makes L ambiguous.

Your first example is unambiguous because neither of "A", "B", "C" is prefix of another.

In your second example, because L contains "Pop" and "Popcorn", you add "corn" to S. And "corn" is an element of S, so it's ambigous. In your third example, we also add "corn" to S, but L contains no prefix of "corn" and no string that starts with "corn", so we are finished and L is unambiguous.

  • Oooh, this is what I'm looking for. I'm not sure what you are saying with your last paragraph. Can you give an example as to when you'd have to test the extensions a second time? – Nathan Merrill Feb 19 '16 at 16:21
1

I think the structure you are looking for is a 'Trie' commonly used for auto complete, spell checking etc.

In your case a trie which is flat, ie no node has a child node, should equate to none of the words being a substring at the start of any of the others and hence your ablity to ommit a delimiter.

In the case of 'pop' and 'popcorn' but no 'corn' you need to check for both duplicate nodes in the trie. And nodes which are not words

Ie i have pop->corn but only one instance of each

where as if I add the word 'orn' I would have root -> pop->c->orn and root->orn but a non word node 'c'

If I add 'corn' I have root->pop->corn and root->corn. With no non words

Hmmm no thinking about it perhaps not...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.