Fwd: Bloomberg interview questions 2/13/2015 {XR

String getRegularExpression(String str1, String str2);
Base on input 2 strings, return a regex String that can cover 2 input strings.
e.g "Bloomberg", "BloomingDale" should output "Bloom.*g.*"


I proposed a solution:
step 1: find out common segments of the 2 strings
step 2: insert ".*" in between the common segments to form a string

He asked: how to find the common segments?
also he let me think of below examples, but I really couldn't find any
clue from his example.
"Bloomberg", "BloomingDale"
"StarBucksCoffee", "RedCoffee"

In the end, he said my proposed solution is not technically optimized.
Obviously, he has better solution, but he didn't give me the hint.
So I still have no idea at all.

Can you think of a solution?