CODEWITHSUNDEEP
algorithm
Anthony
Anthony

Reputation: 35978

How to split a word into different ways such that it is a concatenation of two other words

I just came across this interesting question online and am quite stumped as to how to even progress on it. 

Write a function that finds all the different ways you can split up a word into a
concatenation of two other words.

Is this something that Suffix Trees are used for?

I'm not looking for code, just conceptual way to move forward with this.

Upvotes: 1

Views: 725

Answers (3)

sudhakar shah
sudhakar shah

Reputation: 1

Total number of different ways to do it can be greater than one if and only if this condition holds:

-> one of the two words must be a multiple of other. For eg: "abcd" and "abcdabcd". Using these two words u can form the string "abcdabcdabcdabcd" in many different ways.

So first check this condition.

Then check whether the string can be written from the two words in any way. Then simple math should give you the answer

Upvotes: -2

dharam
dharam

Reputation: 8096

If you are looking for a nice answer then please let us know your definition of a valid word.

Assuming a word is a string defined over an alphabet and has length greater than zero. You can use suffix trees.

Below is a simplified algorithm which will take just O(n) time.

Convert the word into a character array.

Traverse through the length of the array and for each i just take two strings (0 to i) and 
(i+1     to    length of the array-1).

Do remember to cover the base conditions like length greater than zero.

Upvotes: 2

Colin D
Colin D

Reputation: 5661

some psuedocode: 

   foreach place you can split the word:
    split the word.
    check if both sides are valid words.

Upvotes: 6

Related Questions