Programming Interview Questions 6: Combine Two Strings

Again a nice question and a good solution but I guess there is a better solution. We’ll use 3 indices, like merge sort, initially pointing the beginning of each strings. Lets say them i1,i2 and i3 respectively. We will iterate i3 from 0 to len(str3). In each iteration increment i1 if str1[i1]==str3[i3], or increment i2 if str2[i2] == str[i3]. If neither these two conditions satisfied then str3 is not a valid shuffling. We don’t need to check other characters in str1 and str2 because we shouldn’t see str1[i1+j] before str1[i1] or str2[i2+k] before str2[i2]. If iteration finishes then this is a valid shuffle. This gives us O(N+M) time complexity and O(1) space complexity. Also we didn’t use heap stack as well. In your solution, if strings are too long we may fill up heap stack.

I like your interview question series. keep up writing :))

Hi Arden,

I wonder if it would be possible to keep only the index number of failing string compared to original one in the cache instead of whole substring. For your example, it would cache the string tuple as {bc,f}, for some time rigth? Instead, would it be possible to cache {1,2} meaning that 1 is the substring of abc from the index 1 and so on.

Nice solution :)

String 1 : bcde
String 2 : acfg
String 3 : abcfcdeg
String 3 is a valid string

in case of a tie let the algorithm pic the character from the first string in other words string1++
so the algorithm goes picks the character in this manner:
string 2(a) , string 1(b) , string 1(c)….
now the next character to be matched is ‘f ‘
but it is cannot be since string1 is now pointing to d
and string2 is pointing to c !

same explanation can be used to prove this algorithm wrong : delete the characters in string 3 contained in string 1 and then match string 3 to string 2

so the correct solution is the one arden posted !
and here is where he checks for the both possibilities *s1==*s3 and *s2==*s3

if str1[0]==str3[0] and isShuffle2(str1[1:], str2, str3[1:], cache):
return True
if str2[0]==str3[0] and isShuffle2(str1, str2[1:], str3[1:], cache):
return True


Note that the code here
def isShuffle2(str1, str2, str3, cache=set()):

is a bit dangerous. The default cache value, when modified by any call saves its default value for subsequent calls.

So, the first time you call this function with two arguments (defaulting the cache), it will work as expected. If you call it again with two arguments, the value of cache is the value from the previous call. Almost never what you want. An accepted Python metaphore is to do

def isShuffle2(str1, str2, str3, cache=None):
if cache is None: cache = set()

I am not aware how the cache concept works in C\C++. Can someone please tell me\post the equivalent way for the above soln in C\C++. Appreciate your help!.

I think there is a linear solution

def check_shuffle(s1, s2, s3):
if len(s3) != len(s1) + len(s2):
return False
s1_pos = 0
remains = ”
for index, s in enumerate(s3):
if s1_pos == len(s1):
remains += s3[index:]
break
elif s1[s1_pos] == s:
s1_pos += 1
else:
remains += s
if s1_pos != len(s1):
return False
return remains == s2

Hi Arden,

I had one question about the DP solution. If you are adding to local copy of cache, and returning function, it will not be reflected in the callee function. The cache is always empty. Can you check this?

Thanks.

Here’s my iterative solution written java which handles the case of (str1[i] == str2[i] == shuffledStr[i]) with O(N+M) time complexity and O(N) extra space complexity,

public boolean isCorrectlyShuffled(String str1, String str2,String shuffledStr) {

//handle null strings by converting them to empty strings
str1 = (str1 == null) ? “” : str1;
str2 = (str2 == null) ? “” : str2;
shuffledStr = (shuffledStr == null) ? “” : shuffledStr;

//eliminate some cases by checking string lengths
//and empty-nonempty str1-str2 inputs

if ((str1.length() + str2.length() != shuffledStr.length())
|| ((str1.isEmpty() || str2.isEmpty()) && !(str1 + str2).equals(shuffledStr)))
return false;

//use two index values for two strings
int ind1 = 0;
int ind2 = 0;

//keep a hashmap for the case of (str1[i] == str2[i] == shuffledStr[i])
Map charBackup = new HashMap();

for (int i = 0; i < shuffledStr.length(); i++) {
//count occurences of a char at current indexes of three strings
int occurence = 0;
char currChar = shuffledStr.charAt(i);

if (ind1 < str1.length() && currChar == str1.charAt(ind1)) {
ind1++;
occurence++;
}

if (ind2 0) {
occurence++;
charBackup.put(currChar, –backupLimit);
}

//if a char occured more than once, add the char to the hashmap
//to be used later as a backup
if (occurence == 2) charBackup.put(currChar, backupLimit + 1);

else if (occurence == 0) return false;
}

return true;
}