1662. Check If Two String Arrays are Equivalent

EasyArrayString

Problem Description

This problem presents two arrays, word1 and word2, each containing strings. The task is to determine if these two arrays represent the same string when their contents are concatenated together. In other words, if we join all the elements of word1 end-to-end to make a single string and do the same with word2, and those two resulting strings are identical, we should return true. Otherwise, we will return false. It is essential to concatenate the elements in the order they appear in their respective arrays.

Intuition

To solve this problem, we rely on the simple property that strings are equal if they contain the same sequence of characters in the same order. Therefore, the solution approach is straightforward:

Concatenate all elements in word1 to form a single string.
Concatenate all elements in word2 to form another single string.
Compare these two strings for equality.

If both strings are equal, it means the arrays word1 and word2 represent the same string; thus, we return true. If they differ, the arrays represent different strings, so we return false. This is achieved with minimal code by using the join method in Python, which concatenates the elements of a list into a string, separated by the string provided to join (in this case, an empty string as we don't want any characters between the elements).

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimumsAdd a heap to store the minimumsAdd a variable to track the minimumAdd a queue to store the minumums

I don’t know

Solution Approach

The implementation of the solution is straightforward and elegant, thanks to Python's high-level string handling capabilities. The algorithm does not rely on complex data structures or patterns; it primarily uses the built-in string functionality provided by Python.

Here's a step-by-step walk-through of the arrayStringsAreEqual function within the Solution class:

The join method is called on an empty string ('') with word1 as the argument. The join method takes all elements in word1, which are strings themselves, and concatenates them in the order they appear in the array. This results in a single string that represents the concatenation of all individual strings in word1.

joined_word1 = ''.join(word1)
The same process is applied to word2:

joined_word2 = ''.join(word2)
Now, we have two strings represented by joined_word1 and joined_word2. All that remains is to check whether these two strings are identical.

result = joined_word1 == joined_word2
The result of this comparison is a boolean (True or False). The function directly returns this result, completing the check with a single line of code:

return joined_word1 == joined_word2

This approach takes full advantage of Python's ability to handle strings and perform operations on lists. It effectively reduces what could be a more complex algorithm involving manual iteration and concatenation to a simple one-liner that is easy to understand and maintain.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

Example Walkthrough

Let's consider an example where word1 = ["ab", "c"] and word2 = ["a", "bc"]. We need to follow the described solution approach to determine if these two arrays represent the same string when concatenated.

First, we concatenate the elements of word1 using the join method on an empty string.

1joined_word1 = ''.join(["ab", "c"])  # This evaluates to "abc"

After applying the join method, we end up with the string "abc".

Next, we concatenate the elements of word2.

1joined_word2 = ''.join(["a", "bc"])  # This evaluates to "abc"

Similarly, the join method results in the string "abc" for word2.

Now we have both strings obtained from word1 and word2 respectively. We will now compare these two strings to check if they are identical:
```
1result = joined_word1 == joined_word2  # This evaluates to True
```
In this case, joined_word1 is "abc" and joined_word2 is also "abc". The comparison yields True.
Finally, we will directly return the result of the comparison:
```
1return result  # This returns True
```
Since result was True, the function would return True, indicating that word1 and word2 do indeed represent the same string when concatenated.

Therefore, given the inputs word1 = ["ab", "c"] and word2 = ["a", "bc"], the function arrayStringsAreEqual will return True, as the concatenated strings from both arrays are identical.

Solution Implementation

1from typing import List  # Import the List type from typing module for type annotations
2
3class Solution:
4    def array_strings_are_equal(self, word1: List[str], word2: List[str]) -> bool:
5        """
6        Checks if the strings from two lists are equal when concatenated.
7      
8        Parameters:
9        word1 (List[str]): First list of strings.
10        word2 (List[str]): Second list of strings.
11      
12        Returns:
13        bool: True if the concatenated strings are equal, False otherwise.
14        """
15        # Concatenate all strings in the first list and compare with the concatenation of the second list
16        return ''.join(word1) == ''.join(word2)
17

1class Solution {
2
3    /**
4     * Checks if two string arrays are equal when their elements are concatenated.
5     * @param wordArray1 The first array of strings.
6     * @param wordArray2 The second array of strings.
7     * @return true if the concatenated strings are equal, false otherwise.
8     */
9    public boolean arrayStringsAreEqual(String[] wordArray1, String[] wordArray2) {
10        // Join the elements of the first array into a single string
11        String concatenatedWord1 = String.join("", wordArray1);
12      
13        // Join the elements of the second array into a single string
14        String concatenatedWord2 = String.join("", wordArray2);
15      
16        // Compare the two concatenated strings for equality
17        return concatenatedWord1.equals(concatenatedWord2);
18    }
19}
20

1#include <vector>
2#include <string>
3#include <numeric> // Required for std::accumulate
4
5class Solution {
6public:
7    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
8        // Convert the first vector of strings into a single string
9        std::string concatenatedWord1 = std::accumulate(word1.begin(), word1.end(), std::string(""));
10      
11        // Convert the second vector of strings into a single string
12        std::string concatenatedWord2 = std::accumulate(word2.begin(), word2.end(), std::string(""));
13      
14        // Compare the two concatenated strings and return whether they are equal
15        return concatenatedWord1 == concatenatedWord2;
16    }
17};
18

1// This function checks if two arrays of strings are equivalent after combining their elements.
2// @param {string[]} firstWordArray - The first array of strings to be compared.
3// @param {string[]} secondWordArray - The second array of strings to be compared.
4// @return {boolean} - Returns true if the concatenated strings are equal, otherwise false.
5function arrayStringsAreEqual(firstWordArray: string[], secondWordArray: string[]): boolean {
6    // Concatenate the elements of the first array into a single string
7    const firstCombinedString = firstWordArray.join('');
8  
9    // Concatenate the elements of the second array into a single string
10    const secondCombinedString = secondWordArray.join('');
11  
12    // Compare the concatenated strings for equality and return the result
13    return firstCombinedString === secondCombinedString;
14}
15

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

The time complexity of the code is O(m + n) where m is the total number of characters in word1 and n is the total number of characters in word2. This is because the join operations for word1 and word2 each iterate over their respective arrays to build a single string, which takes linear time relative to the number of characters in each array.

The space complexity of the code is O(m + n) as well, since it needs to allocate space for the new strings generated by ''.join(word1) and ''.join(word2). No additional space is required beyond the strings themselves.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First SearchBreadth-First SearchBinary SearchPriority Queue

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1662. Check If Two String Arrays are Equivalent

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings