algoadvance

Leetcode 1662. Check If Two String Arrays are Equivalent

Problem Statement

You are given two string arrays word1 and word2. A string array represents a sentence by concatenating its elements in order. Return true if the two sentences represented by the two arrays are the same and false otherwise.

Example 1:

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

Example 2:

Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false
Explanation: 
word1 represents "a" + "cb" -> "acb"
word2 represents "ab" + "c" -> "abc"
The strings are not the same, so return false.

Example 3:

Input: word1 = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true
Explanation: 
word1 represents "abc" + "d" + "defg" -> "abcddefg"
word2 represents "abcddefg" -> "abcddefg"
The strings are the same, so return true.

Constraints:

Clarifying Questions

  1. What should be returned if both word1 and word2 are empty?
    • Based on the problem statement and typical use cases, if both arrays are empty, returning true would make sense because empty strings are equal.

Strategy

  1. Concatenate Strings:
    • Concatenate the elements of word1 to form a single string.
    • Concatenate the elements of word2 to form a single string.
  2. Compare the Resulting Strings:
    • Simply compare the two resulting strings for equality.

Code Implementation

#include<vector>
#include<string>
#include<iostream>

using namespace std;

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
    string str1 = "";
    string str2 = "";
    
    for (string w : word1)
        str1 += w;

    for (string w : word2)
        str2 += w;

    return str1 == str2;
}

// Main function for testing
int main() {
    vector<string> word1 = {"ab", "c"};
    vector<string> word2 = {"a", "bc"};
    cout << (arrayStringsAreEqual(word1, word2) ? "true" : "false") << endl; // true

    word1 = {"a", "cb"};
    word2 = {"ab", "c"};
    cout << (arrayStringsAreEqual(word1, word2) ? "true" : "false") << endl; // false

    word1 = {"abc", "d", "defg"};
    word2 = {"abcddefg"};
    cout << (arrayStringsAreEqual(word1, word2) ? "true" : "false") << endl; // true

    return 0;
}

Time Complexity

The time complexity of this approach is O(N), where N is the total number of characters in both word1 and word2. This is because concatenating all the strings involves iterating through every character in both arrays. Comparing the resulting strings also involves iterating through each character, but this is effectively linear.

The space complexity is also O(N) due to the storage required for the concatenated strings.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI