Leet Code 75–1768. Merge Strings Alternately

As part of the Leet Code 75, this is an easy problem with the description being:

You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

Example 1:

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"

Explanation: The merged string will be merged as so:
word1: a b c
word2: p q r
merged: a p b q c r

Example 2:

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"

Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1: a b
word2: p q r s
merged: a p b q r s

Example 3:

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"

Explanation: Notice that as word1 is longer, "cd" is appended to the end.

word1: a b c d
word2: p q
merged: a p b q c d

Constraints:

1 <= word1.length, word2.length <= 100
word1 and word2 consist of lowercase English letters.

As the name of the problem says, what you have to do is merge both strings, character by character in an alternate way.

String Builder is the most recommended way to do since it avoids creation of new Strings instances (which is bad for memory and performance), and also I would recommend use of for instead of while since could be that anything might occur and cause an infinite loop, so always look for usage of iterations instead of while operations.

class Solution {
    public String mergeAlternately(String word1, String word2) {

        final StringBuilder builder = new StringBuilder();
        final int maxLength = word1.length() > word2.length() ? word1.length() : word2.length();

        for(int i=0;i<maxLength;i++) {
            if(i < word1.length()) builder.append(word1.charAt(i));
            if(i < word2.length()) builder.append(word2.charAt(i));
        }

        return builder.toString();
    }
}

Runtime: 1 ms, faster than 78.59% of Java online submissions for Merge Strings Alternately.

Memory Usage: 40.6 MB, less than 85.42% of Java online submissions for Merge Strings Alternately.

First we create the builder, then get that maximum possible length (either word1 or word2) using a ternary operator, afterwards we iterate it from zero to the maximum length.

On each iteration we check if the index is less than the respective word, if yes then we append the character of that specific index.

In this we could potentially add a try/catch instead of doing an check like this, but this would be bad performance wise, as you can see down bellow:

class Solution {
    public String mergeAlternately(String word1, String word2) {

        final StringBuilder builder = new StringBuilder();

        final int maxLength = word1.length() > word2.length() ? word1.length() : word2.length();

        for(int i=0;i<maxLength;i++) {
            try {
                builder.append(word1.charAt(i));    
            } catch(final IndexOutOfBoundsException ioe){
                // do nothing
            }
            try {
                builder.append(word2.charAt(i));    
            } catch(final IndexOutOfBoundsException ioe){
                // do nothing
            }
        }

        return builder.toString();
    }
}

Runtime: 5 ms, faster than 34.24% of Java online submissions for Merge Strings Alternately.

Memory Usage: 43.5 MB, less than 6.06% of Java online submissions for Merge Strings Alternately.

Both results are O(n), but since we use try/catch on the second solution you see that it takes more memory and also is five times slower than the first one.

So try to avoid try/catch if you want to achieve maximum performance.

That’s it! If there is anything thing else to discuss feel free to drop a comment, if I missed anything let me know so I can update accordingly.

Until next post! :)