How to merger two String in Java

Question

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?

Answer 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;
}

}

Answer 2

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.

Answer 3

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);
}