0

Given two small String of different length and one full String. Check if the full String is merged from two small String.

Example1: Input - "beautiful", "bauful", "eti" Output - true

Example2: Input - "beautiful", "baufl", "eti" Output - false

That means the characters in small String 1 and small String 2 are in the same order as in full String.

Here is my code:

public class StringMerger {
    public static boolean isMerge(String s, String part1, String part2) {
        StringBuilder sb = new StringBuilder();
        int minLength = Math.min(part1.length(), part2.length());
        int maxLength = Math.max(part1.length(), part2.length());
        for(int i = 0; i < minLength; i++){
            sb.append(part1.charAt(i)).append(part2.charAt(i));
        }
        for(int i = minLength; i < maxLength; i++){
            if(part1.length() >= part2.length()) sb.append(part1.charAt(i));
            else sb.append(part2.charAt(i));
        }
        String temp = sb.toString();
        return (temp.equalsIgnoreCase(s)) ? true : false;
    }
}

But I have only solve with: Input - "beautiful", "batfl", "euiu" Output - true. This is only one of that' cases. So how to solve it?

Improve this question
2
  • are in the same order? I guess you mean that you read from left to right, can move the reading between the small strings, but never go backwards. That's what it looks like at least. Commented Oct 18, 2015 at 14:03
  • 1
    I'd recommend writing two test methods first, where you define a number of possible passing and failing Strings. Have them invoke isMerge() (which can just be a no-op) and then develop/debug until the tests all pass. Otherwise you are going to be chasing edge conditions. Commented Oct 18, 2015 at 14:04

3 Answers 3

Reset to default
1

Checkout the below solution, you are welcome to break it

Edit1 Fix bug: the bug is not due to the space, it is because when there is a character match in both small strings, the algorithm need to examine which character to take by checking both alternatives

Edit2 Reduce unnecessary depth first search to improve efficiency

public class StringMerger {

public static void main(String[] args) {
    System.out.println(isMerge("beautiful", "bauful", "eti")); // true
    System.out.println(isMerge("beautiful", "baufl", "eti")); // false
    System.out.println(isMerge("bbbbb", "bbb", "bb")); // true
    System.out.println(isMerge("xyzxyz", "xyz", "xyz")); // true
    System.out.println(isMerge("xyzxyz", "xyz", "xyzd")); // false
    System.out.println(isMerge("backstreetboy", "beetb", "ackstroy")); // true
    System.out.println(isMerge("Can we merge it? Yes, we can!", "Cn w riYes n!", "aemege t? , weca")); //true
    System.out.println(isMerge("beautifulxyzx", "baufulx", "etixyz")); // true
}

public static boolean isMerge(String s, String part1, String part2) {
    if (s.length() != part1.length() + part2.length()) return false;

    int part1Counter = 0;
    int part2Counter = 0;
    int fullStrLen = s.length();

    int fullStrCounter = 0;

    while (fullStrCounter < fullStrLen) {

        boolean part1match = part1Counter < part1.length() && s.charAt(fullStrCounter) == part1.charAt(part1Counter);
        boolean part2match = part2Counter < part2.length() && s.charAt(fullStrCounter) == part2.charAt(part2Counter);
        if (part1match && part2match) { // if find a match in both substring, we need to find out whichever way works
            boolean decision1 = isMerge(s.substring(fullStrCounter + 1), part1.substring(part1Counter + 1), part2.substring(part2Counter));
            if (decision1) return decision1; // no need to check the second branch if the first branch matches
            boolean decision2 = isMerge(s.substring(fullStrCounter + 1), part1.substring(part1Counter), part2.substring(part2Counter + 1));
            return decision2;
        }
        if (part1match) {
            ++part1Counter;
            ++fullStrCounter;
        } else if (part2match) {
            ++part2Counter;
            ++fullStrCounter;
        } else {
            return false;
        }
    }
    return true;
}

}

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Here comes feature creep! Seriously, @khuong291, you need to specify requirements early on. Anyway, you have a basic algorithm with example code. Surely you should be able to handle (or ignore) spaces?
@khuong291 agree with jdv, this is a feature creep. But can you give an example where space will not work? The code above doesn't care about space.
I will handle it, but I will show u 1 case that your code doesn't work for me. "Can we merge it? Yes, we can!", "Cn w riYes n!", "aemege t? , weca" --> return true.
And I agree the above code has missed some cases, I'll try to work it out.
1

Here's a shorter method. It makes use of Arrays.

private static boolean isMerge(String original, String one, String two){

    String combinedStrings = one + two;
    char[] mergedStrings = combinedStrings.toCharArray();
    char[] originalString = original.toCharArray();

    Arrays.sort(mergedStrings);
    Arrays.sort(originalString);

    return Arrays.equals(mergedStrings, originalString);
}
Improve this answer

8 Comments

Your question does seem to send off a "homework" vibe but I'll just be a nice guy and hand it over to you.
Does this satisfy the requirement that the two candidate Strings list chars ordered the same as the word String? I think this is only testing the same chars are found in the merged vs. original String.
I'm not sure if you tested it properly. The parameters you commented tested true with me.
That's very nice, I got your idea. But I have 1 more case (plus) that doesn't work, please help me. "beautiful", "beau", "tiflu" --> return false. It must order from each String.
Oh I get you know. This would be very difficult since you can't really or it will be hard to make a loop that will test all possible patterns. It would be a wild card since the parameters could be in different orders or so. You get the gist.
|
1

A possible brute-force starting algorithm, without giving you the solution for your homework:

  • Walk the word String looking for matches in each candidate String.
  • If there is no match (or both Strings are exhausted), then return False.
  • If there is a match, move the index for this candidate String.
  • If we exhaust the word String and all candidate Strings, return True.

I'm hand-waving past the edge conditions here, which would ideally be caught by tests.

It occurs to me that this class should be able to generate candidate Strings from any word String, meaning that you could even make the class symmetric.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.