TopCoder problem "BlockDistance" used in SRM 306 (Division II Level Three)



Problem Statement

    

The block distance from oldText to newText is defined as the least number of block insertions in oldText that are needed to make it equal to newText. A block insertion into oldText is the insertion of any string at any position. For example, if oldText is "herld" a possible block insertion is inserting "llo wo" before the 'r' which will give "hello world".

As an example, if oldText is "hello goodbye" and newText is "hello, how are you? goodbye have a nice day", the block distance between them is 2 because by inserting ", how are you? " and " have a nice day" properly, we can make oldText equal to newText.

You will be given oldText and newText as two String[]s. You must first concatenate all the elements within each of them to form two long strings, and then return the block distance between them. If there is no way to make oldText equal to newText using only block insertions, return -1.

 

Definition

    
Class:BlockDistance
Method:minDist
Parameters:String[], String[]
Returns:int
Method signature:int minDist(String[] oldText, String[] newText)
(be sure your method is public)
    
 

Constraints

-oldText and newText will each have between 1 and 20 elements, inclusive.
-Each element of oldText and newText will have between 1 and 50 characters, inclusive.
-Each character of each element of oldText and newText will have an ASCII value between 32 and 126, inclusive.
 

Examples

0)
    
{"hello goodbye"}
{"hello, how are you? goodbye have a nice day"}
Returns: 2
The example from the problem statement.
1)
    
{"aaaaa"}
{"ababababa"}
Returns: 4
Every b has to be added in a different block.
2)
    
{"aaaaaaaaaaaaaaaa"}
{"aaaaaaaaaaaaaaaa","t","aaaaaaaaaaaaaaaa"}
Returns: 1
3)
    
{"no way"}
{"No way!"}
Returns: -1
4)
    
{"abce","f","ij","klm","n","op","uvwx","z"}
{"ab","cdefg","hijklmnop","q","rs","tuv","wxyz"}
Returns: 4
You need to insert "d" before the 'e', "gh" before the 'i', "qrst" before the 'u' and "y" before the 'z'.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6417

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9986&pm=6417

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , Olexiy , lovro , Andrew_Lazarev

Problem categories:

Dynamic Programming