Jobs

Interviews

Discussions

Check If Two String Arrays are Equivalent

Easy

Asked by:

More companies

15 views

Topics:

ArraysStringsTwo Pointers

Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.

A string is represented by an array if the array elements concatenated in order forms the string.

Example 1:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

Example 2:

Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false

Example 3:

Input: word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true

Constraints:

1 <= word1.length, word2.length <= 10³
1 <= word1[i].length, word2[i].length <= 10³
1 <= sum(word1[i].length), sum(word2[i].length) <= 10³
word1[i] and word2[i] consist of lowercase letters.

Try coding it in LeetCode

Check If Two String Arrays are Equivalent

Easy

Asked by:

15 views

Topics:

ArraysStringsTwo Pointers

Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.

A string is represented by an array if the array elements concatenated in order forms the string.

Example 1:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

Example 2:

Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false

Example 3:

Input: word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true

Constraints:

1 <= word1.length, word2.length <= 10³
1 <= word1[i].length, word2[i].length <= 10³
1 <= sum(word1[i].length), sum(word2[i].length) <= 10³
word1[i] and word2[i] consist of lowercase letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input arrays contain null or empty strings?
What are the size constraints for the input arrays and the strings within them?
Are the strings in the arrays expected to contain only alphanumeric characters, or can they contain special characters or whitespace?
Is case sensitivity important when comparing the concatenated strings? Should I treat "abc" and "ABC" as equivalent?
If one of the arrays is null or empty, what should the return value be?

Brute Force Solution

Approach

The brute force approach to checking if two sets of word lists represent the same combined sentence is simple. We will build the full sentence from each list of words and then compare the two full sentences. If they are equal, the original word lists are equivalent.

Here's how the algorithm would work step-by-step:

First, take all the words from the first list and combine them into one big sentence.
Next, do the same thing with the second list of words, creating another big sentence.
Finally, check if the two big sentences are exactly the same, character for character.
If they match perfectly, then the original lists of words are considered equivalent.

Code Implementation

def array_strings_are_equal(word_list1, word_list2):
    # Build the first string from the first array.
    first_combined_string = "".join(word_list1)

    # Build the second string from the second array.
    second_combined_string = "".join(word_list2)

    # Compare the two strings to check for equality.
    if first_combined_string == second_combined_string:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(N) – The algorithm iterates through each word in word1 and word2 to construct two strings. Let N be the total number of characters across all words in both input arrays. Building each string takes O(N/2) time in the worst case, and comparing the two resultant strings takes O(N) time. Therefore, the overall time complexity is O(N/2) + O(N/2) + O(N) which simplifies to O(N).

Space Complexity

O(N) – The algorithm constructs two new strings by concatenating the words from the input arrays. The size of each new string is proportional to the total number of characters in each corresponding input array. In the worst case, the total number of characters in each input array is N/2, where N is the total number of characters in both arrays, giving a space complexity of O(N/2 + N/2) which simplifies to O(N).

Optimal Solution

Approach

Instead of actually combining the string arrays into single strings, the efficient approach compares them piece by piece. Imagine reading the two arrays simultaneously, checking if they match character by character as you 'read' them.

Here's how the algorithm would work step-by-step:

Imagine two readers, one for each string array.
Both readers start at the beginning of their respective arrays and at the beginning of the first string in their arrays.
Compare the characters that each reader is currently pointing at. If they're different, the arrays are not equivalent.
If the characters match, both readers move to the next character in their respective strings.
If a reader reaches the end of a string in its array, it moves to the beginning of the next string in that array.
Keep going until both readers have reached the end of their respective arrays. If all characters matched along the way, the arrays are equivalent.

Code Implementation

def arrayStringsAreEqual(word_array1, word_array2):
    array1_index = 0
    array2_index = 0
    string1_index = 0
    string2_index = 0

    while array1_index < len(word_array1) and array2_index < len(word_array2):
        # Compare characters at current indices
        if word_array1[array1_index][string1_index] != word_array2[array2_index][string2_index]:
            return False

        string1_index += 1
        if string1_index == len(word_array1[array1_index]):
            # Move to the next string in word_array1
            array1_index += 1
            string1_index = 0

        string2_index += 1
        if string2_index == len(word_array2[array2_index]):
            # Move to the next string in word_array2
            array2_index += 1
            string2_index = 0

    # Check if both arrays have been fully traversed
    if array1_index < len(word_array1) or array2_index < len(word_array2):
        return False

    return True

Big(O) Analysis

Time Complexity

O(N) – The algorithm iterates through both string arrays simultaneously, comparing characters one by one. In the worst case, it must examine every character in both arrays to determine equivalence. The total number of character comparisons is directly proportional to the total number of characters across both arrays, which we can collectively define as N. Therefore, the time complexity is O(N).

Space Complexity

O(1) – The provided algorithm uses a constant amount of extra space. It only stores a few integer variables to keep track of the current position within the two string arrays: specifically, the index of the current string within each array, and the index of the current character within each string. The space required for these variables does not depend on the size of the input string arrays; therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Both input arrays are null	Return true because both represent an empty string.
One array is null, the other is not	Return false because they cannot represent the same string.
Both input arrays are empty	Return true because both represent an empty string.
One array is empty, the other is not	Return false because they cannot represent the same string.
One array contains empty strings, the other does not	The concatenation of the first array would be an empty string (''), while the second would not, so return false.
Arrays contain very long strings that may exceed memory limits when concatenated	Iterate through strings instead of concatenating them to avoid memory overflow.
Arrays contain Unicode or other special characters	Ensure the string comparison method correctly handles Unicode and special characters.
Input arrays are extremely large, causing performance issues	The solution should have linear time complexity, making it scale well with large arrays.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input arrays contain null or empty strings?
What are the size constraints for the input arrays and the strings within them?
Are the strings in the arrays expected to contain only alphanumeric characters, or can they contain special characters or whitespace?
Is case sensitivity important when comparing the concatenated strings? Should I treat "abc" and "ABC" as equivalent?
If one of the arrays is null or empty, what should the return value be?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, take all the words from the first list and combine them into one big sentence.
Next, do the same thing with the second list of words, creating another big sentence.
Finally, check if the two big sentences are exactly the same, character for character.
If they match perfectly, then the original lists of words are considered equivalent.

Code Implementation

def array_strings_are_equal(word_list1, word_list2):
    # Build the first string from the first array.
    first_combined_string = "".join(word_list1)

    # Build the second string from the second array.
    second_combined_string = "".join(word_list2)

    # Compare the two strings to check for equality.
    if first_combined_string == second_combined_string:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine two readers, one for each string array.
Both readers start at the beginning of their respective arrays and at the beginning of the first string in their arrays.
Compare the characters that each reader is currently pointing at. If they're different, the arrays are not equivalent.
If the characters match, both readers move to the next character in their respective strings.
If a reader reaches the end of a string in its array, it moves to the beginning of the next string in that array.
Keep going until both readers have reached the end of their respective arrays. If all characters matched along the way, the arrays are equivalent.

Code Implementation

def arrayStringsAreEqual(word_array1, word_array2):
    array1_index = 0
    array2_index = 0
    string1_index = 0
    string2_index = 0

    while array1_index < len(word_array1) and array2_index < len(word_array2):
        # Compare characters at current indices
        if word_array1[array1_index][string1_index] != word_array2[array2_index][string2_index]:
            return False

        string1_index += 1
        if string1_index == len(word_array1[array1_index]):
            # Move to the next string in word_array1
            array1_index += 1
            string1_index = 0

        string2_index += 1
        if string2_index == len(word_array2[array2_index]):
            # Move to the next string in word_array2
            array2_index += 1
            string2_index = 0

    # Check if both arrays have been fully traversed
    if array1_index < len(word_array1) or array2_index < len(word_array2):
        return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both input arrays are null	Return true because both represent an empty string.
One array is null, the other is not	Return false because they cannot represent the same string.
Both input arrays are empty	Return true because both represent an empty string.
One array is empty, the other is not	Return false because they cannot represent the same string.
One array contains empty strings, the other does not	The concatenation of the first array would be an empty string (''), while the second would not, so return false.
Arrays contain very long strings that may exceed memory limits when concatenated	Iterate through strings instead of concatenating them to avoid memory overflow.
Arrays contain Unicode or other special characters	Ensure the string comparison method correctly handles Unicode and special characters.
Input arrays are extremely large, causing performance issues	The solution should have linear time complexity, making it scale well with large arrays.