1. Question
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 rExample 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 sExample 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 d2. Thoughts
3. Tips learned
3.1. str.length() is a member variable
From asking to GPT, I found:
For std::string, you don’t need to manually check for the end, because std::string internally handles the length.
This meant that:
Calling str.length() (or str.size()) on a std::string is O(1).
This is because in the implementation of std::string, the length of the string is stored as a member variable. So, when you call length(), it simply returns this value, without having to iterate through the characters in the string. This makes the operation constant time, or O(1).
The reason this is efficient is that the std::string class keeps track of the length as it manipulates the string, so it doesn't need to recompute it when you ask for it.
And this can be done by:
#include <iostream>
#include <string>
int main() {
std::string str = "Hello, World!";
std::cout << "Length of the string: " << str.length() << std::endl;
// Alternatively:
std::cout << "Size of the string: " << str.size() << std::endl;
return 0;
}
3.2. min
C++ provides a built-in function for finding the minimum of two values, called std::min. This function is part of the <algorithm> header and can be used to return the smaller of two values.
Syntax:
std::min(a, b);aandbcan be any data type that supports comparison (integers, floating-point numbers, strings, etc.).
3.3. Append to String
In C++, you can append a single character to a std::string using either the += operator or the push_back() function. Here's how you can append a character to a string:
1. Using the += Operator:
You can directly append a character to a std::string using the += operator, which works for both strings and individual characters.
#include <iostream>
#include <string>
int main() {
std::string str = "Hello";
// Append a single character
str += '!';
std::cout << str << std::endl; // Output: Hello!
return 0;
}2. Using the push_back() Method:
The push_back() function is specifically designed to append a single character to the end of a std::string.
#include <iostream>
#include <string>
int main() {
std::string str = "Hello";
// Append a single character
str.push_back('!');
std::cout << str << std::endl; // Output: Hello!
return 0;
}3. Using the append() Method:
Although append() is more commonly used to append strings, it can also be used to append a single character by passing a character and a count.
#include <iostream>
#include <string>
int main() {
std::string str = "Hello";
// Append a single character
str.append(1, '!');
std::cout << str << std::endl; // Output: Hello!
return 0;
}Key Points:
+=Operator: Simple and intuitive way to append characters or strings.push_back(): Designed for adding a single character to the end of a string.append(1, 'char'): Allows you to specify how many times to append the character.
Each of these methods is efficient for appending a single character to a std::string. You can choose whichever approach feels more natural for your use case!
3.5. Substring
In C++, you cannot directly use Python-like slicing syntax such as word1[3:] to extract a substring. However, you can achieve similar functionality using the substr() function of the std::string class.
Example: Extracting Substrings in C++
If you want to get a substring starting from index 3 to the end of the string, you can use the substr() function.
Syntax of substr():
std::string substr(size_t pos = 0, size_t len = npos) const;pos: The starting position (index) of the substring.len: The number of characters to extract. If omitted, it will extract till the end of the string.
Example Code:
Here’s how you can achieve the equivalent of word1[3:] in C++:
#include <iostream>
#include <string>
int main() {
std::string word1 = "Hello, World!";
// Extract the substring starting from index 3 to the end of the string
std::string sub_str = word1.substr(3);
std::cout << "Substring from index 3: " << sub_str << std::endl; // Output: lo, World!
return 0;
}Explanation:
word1.substr(3)returns a substring starting from index3and goes to the end of the string. In this case, it would return"lo, World!".
Slicing with Both Start and End Indices:
If you want to extract a substring from index 3 to a specific length (similar to Python slicing like word1[3:8]), you can specify both the starting index and the length.
#include <iostream>
#include <string>
int main() {
std::string word1 = "Hello, World!";
// Extract a substring starting from index 3 and of length 5
std::string sub_str = word1.substr(3, 5);
std::cout << "Substring from index 3 of length 5: " << sub_str << std::endl; // Output: lo, W
return 0;
}Summary:
- C++ does not support Python-like slicing syntax (
[start:end]), but you can use thesubstr()function to extract substrings. word1.substr(3)is equivalent toword1[3:]in Python. You can also specify a second argument to extract a substring of a specific length.
4. My solution
class Solution {
public:
string mergeAlternately(string word1, string word2) {
int strlen1 = word1.length(), strlen2 = word2.length();
int shorter, shorterlen;
if (strlen1 > strlen2){
shorter = 2;
shorterlen = strlen2;
}
else if(strlen1 < strlen2){
shorter = 1;
shorterlen = strlen1;
}
else{
shorter == -1;
shorterlen=strlen1;
}
string returnword;
int cnt = 0;
while (cnt<shorterlen){
returnword += word1[cnt];
returnword += word2[cnt];
cnt++;
}
if (shorter){
if (shorter == 2){
returnword += word1.substr(cnt);
}
else{
returnword += word2.substr(cnt);
}
}
return returnword;
}
};108/108 cases passed (0 ms)
Your runtime beats 100 % of cpp submissions
Your memory usage beats 85.89 % of cpp submissions (7.8 MB)5. AI Solution and Improvements
Here are a few improvements you can make to your solution to make it more concise and idiomatic in C++:
-
Initialization: You can avoid using separate variables for determining which string is shorter. Instead, you can directly handle the case of appending the remainder after the loop.
-
String appending: Use the more efficient string concatenation and iteration method.
-
Comparison of lengths: You don’t need the extra variable
shorterto determine which string is longer. Simply append the remaining characters from both strings after the alternating merge.
Here is the refactored version of your code:
class Solution {
public:
string mergeAlternately(string word1, string word2) {
string result;
int i = 0, n = word1.size(), m = word2.size();
// Merge letters alternately until the end of one of the strings
while (i < n || i < m) {
if (i < n) result += word1[i];
if (i < m) result += word2[i];
++i;
}
return result;
}
};Explanation of changes:
-
Single loop: We loop through both strings at the same time, checking in each iteration if there are remaining characters in
word1andword2. This simplifies the logic and eliminates the need for a separate condition to append the remainder. -
Efficient concatenation: The string
resultis built up by appending characters from both strings during the loop. If one string is exhausted, the loop will still continue and append characters from the longer string. -
Readability: This version is more concise, easier to follow, and more idiomatic in C++ style. It also avoids unnecessary variables, making the code cleaner.
