Solving an easy LeetCode "Merge Strings Alternately"

Question

I am a C++ dev trying to solve problems in C to practice it, specifically the LeetCode Merge Strings Alternately problem:

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.

Here is my code. I am looking for critiques from experienced folks out there.

char *mergeAlternately(char *word1, char *word2) { int len = strlen(word1) + strlen(word2); bool skip_p1 = false; bool skip_p2 = false; char *result = (char *)malloc(sizeof(char) * (strlen(word1) + strlen(word2) + 1)); char *p1 = word1; char *p2 = word2; for (int i;;) { if (*p1 == '\0') { skip_p1 = 1; } if (*p2 == '\0') { skip_p2 = 1; } if (skip_p1 && skip_p2) { result[i] = '\0'; return result; } else if (skip_p1) { result[i++] = *p2; p2++; } else if (skip_p2) { result[i++] = *p1; p1++; } else { result[i++] = *p1; p1++; result[i++] = *p2; p2++; } } return "SHOULD NEVER REACH HERE"; } int main() { char *word1 = "abc"; char *word2 = "pqr"; char *result = mergeAlternately(word1, word2); printf("Result: %s\n", result); return 0; } 

Answer 1

We are missing includes of headers <stdlib.h> (for malloc()) and <string.h> (for strlen()). Without these, compilation will assume they both return int, which may cause Undefined Behaviour.

Although bool is now part of the core language, we should consider including <stdbool.h> for compatibility with compilers that don't yet support C23.

---

The function needs a good comment to tell its users that it returns a pointer to memory that they need to free(). Unlike many other languages, memory management in C is very manual, and it's vitally important to know who owns memory resources such as this at any given point.

---

We don't intend to modify the contents of the strings that are passed as arguments, so we should declare them const char* (or equivalently, char const* - the order isn't significant).

---

Also, memory allocation with malloc() can fail - a sensible way to deal with that is to return null, and pass the handling on to the caller. Note also that the sizeof operator measures in units of char - so sizeof (char) is tautologically 1.

A better allocation would look like this:

 size_t const len = strlen(word1) + strlen(word2); char *const result = malloc(len + 1); if (!result) { return result; } 

As an aside, note that char *const result means we won't change result to point anywhere else. But we're free to modify the chars that it points to.

---

The skip_p1 and skip_p2 variables are clear in their purpose. Since they are of bool type, it's clearer to assign true rather than 1:

 if (*p1 == '\0') { skip_p1 = true; } if (*p2 == '\0') { skip_p2 = true; } 

We could replace these by declaring the variables within the for loop:

 for (int i;;) { const bool skip_p1 = (*p1 == '\0'); const bool skip_p2 = (*p2 == '\0'); 

---

Although this code shouldn't be reachable, it's problematic on two counts:

 return "SHOULD NEVER REACH HERE"; 

Since this string wasn't allocated by malloc(), it's an error for the caller to free() it. And because string literals may be stored in read-only memory, we shouldn't use them to initialise char* - only char const*.

I might include <assert.h> and replace with

 assert(!"unreachable"); free(result); return NULL; 

That said, I'm happy to trust my compiler's warnings and omit that part entirely. If there's a way it can be reached, I'll get a warning that we fail to return a value in that path.

---

As to the algorithm, it's reasonably clear. One thing we might want to consider is that when one of the strings ends, then we can just strcpy() the other into the output (even if the other string has also ended, as that's a good way to add the terminating null character).

---

Modified code

Taking all the above into account, we get something that looks very different from the original. But I hope it's educational.

#include <stdlib.h> #include <string.h> /* * Create a new string formed by alternating the letters of s1 and s2. * The returned string comes from malloc(); caller must call free(). * Returns a null pointer if allocation fails. */ char *mergeAlternately(char const *s1, char const *s2) { size_t const len = strlen(s1) + strlen(s2); char *const result = malloc(len + 1); if (!result) { return result; } char *out = result; for (;;) { if (*s1 == '\0') { strcpy(out, s2); return result; } if (*s2 == '\0') { strcpy(out, s1); return result; } *out++ = *s1++; *out++ = *s2++; } } 

It's always helpful to have a test program that illustrates how to use the function correctly:

#include <stdio.h> int main() { char *merged = mergeAlternately("AAA", "bbbbb"); if (!merged) { fprintf(stderr, "Allocation failure\n"); return EXIT_FAILURE; } printf("Merged result: %s\n", merged); free(merged); } 

Answer 2

Let us compare it with a straight simplistic solution in your style.

char *mergeAlternately(char *word1, char *word2) { int len = strlen(word1) + strlen(word2); char *result = (char *)malloc(sizeof(char) * (strlen(word1) + strlen(word2) + 1)); char *p1 = word1; char *p2 = word2; char *p = result; while (*p1 || *p2) { if (*p1) { *p = *p1; p++; p1++; } if (*p2) { *p = *p2; p++; p2++; } } *p = '\0'; return result; } 

So due to the missing skip variables*p1 and *p2 are repeated twice.

The if *p1 and if *p2 are separately executed, not in an if-else if-else chain. This safes an else and repetititions of copying *p1 and *p2. Also you were almost forced to terminate the merged string inside the loop.

Now you need no artifact return "..."; which might be unreachable, but a code style checker might see a non-freeable result.

The loop condition is telling "end reached of p1 resp. p2."

I have replaced usage of an index i in result with a pointer p - just as you did for word1 and word2.

Personally I am not a friend of the alternative style:

if (*p1) { *p++ = *p1++; } 

What really could be considered:

When one of the words is very short, then on reaching one end you could just copy the other and exit the loop.

for (;;) { if (!*p1) { strcpy(p, p2); break; } if (!*p2) { strcpy(p, p1); break; } *p = *p1; p++; p1++; *p = *p2; p++; p2++; } return result; 

Merge "a" with "zzz.....zzz" and the second solution will be considerably faster.

It also does away with providing a NUL terminator oneself and if statements.

This also teaches a lesson on premature optimization as the skip... variables are no longer needed. Best style is to declare variables near their first usage: the code becomes better readable and modifiable.

Answer 3

General Observations

The code compiles as long as you add the missing header files. There is one warning message when compiled with the -Wall -Wextra -pedantic flags. The variable len is assigned a value but never used.

There is insufficient testing, only one test where the strings are both of the same length. Testing should be done in a loop, tests should include a test where either string is empty, and where both strings are empty.

This program is leaking memory badly: the allocated string is never freed.

The boolean variables are not needed, so stdbool.h doesn't need to be included.

For optimal performance, use a pointer for the result string rather than using an index.

Test the input strings before using strlen() or malloc(). If either string is empty return the string that has a value; there is no need to malloc() in this case. If both strings are empty there is also no reason to allocate memory.

There is no reason to cast the result of the call to malloc().

Test for Possible Memory Allocation Errors

In modern high-level languages such as C++, memory allocation errors throw an exception that the programmer can catch. This is not the case in the C programming language. While it is rare in modern computers because there is so much memory, memory allocation can fail, especially if the code is working in a limited memory application such as an embedded control system. In the C programming language when memory allocation fails, the functions malloc(), calloc() and realloc() return null. Referencing any memory address through a null pointer results in undefined behavior (UB).

Possible unknown behavior in this case can be a memory page error (in Unix this would be called a Segmentation Violation), corrupted data in the program, and in very old computers it could even cause the computer to reboot (corruption of the stack pointer).

To prevent this undefined behavior a best practice is to always follow the memory allocation statement with a test that the pointer that was returned is not null.

Convention When Using Memory Allocation in C

When using malloc(), calloc() or realloc() in C, a common convention is to use sizeof *PTR rather sizeof (PTR_TYPE); this makes the code easier to maintain and less error-prone, since less editing is required if the type of the pointer changes.

 char *result = malloc(sizeof(*result) * (strlen(word1) + strlen(word2) + 1)); 

Incorrect Type Used for Size

The variables len and i should both be of type size_t. This is the type that strlen() returns and that malloc() expects as input.

Answer 4

The previous answers cover the major review points. Here are some minor style suggestions.

---

When working on programming challenges like this, the focus is on correct functionality and efficiency, and rightly so. However, coding style is usually an afterthought.

Documentation

Add a comment to the top of the code to summarize its purpose. Something like the text in the question is appropriate.

Indentation

Code that only uses 2 spaces per indent level is hard to read. Using 4 spaces per level is much easier to read.

Consistency

In one place you set the boolean variable to the value false:

bool skip_p1 = false; 

then later set it to an integer:

skip_p1 = 1; 

Let's go for a little consistency and use:

skip_p1 = true; 

Naming

The variable name result is a bit generic. Perhaps something like merged_word would be more specific.

Answer 5

Many good review points already.

Yet I thought code should take advantage that it knows the lengths and so can reduce testing in the loop.

Keeping track of the lengths also affords an overflow check and simplified appending of the longer string.

#include <stdint.h> #include <stdlib.h> #include <string.h> char *mergeAlternately_alt(const char *word1, const char *word2) { size_t len1 = strlen(word1); size_t len2 = strlen(word2); if (len1 + 1 > SIZE_MAX - len2) { // Check for 2 _big_ strings return NULL; } char *merged = malloc(len1 + len2 + 1); if (merged == NULL) { // Allocation failure? return NULL; } char *dest = merged; size_t len_min = (len1 < len2) ? len1 : len2; for (size_t i = 0; i < len_min; i++) { *dest++ = *word1++; *dest++ = *word2++; } // Append the rest of the longer word (string). strcpy(dest, (len1 > len2) ? word1 : word2); return merged; }