Leetcode – Check If Two String Arrays are Equivalent Solution

Spread the love

The problem “Check If Two String Arrays are Equivalent” is an excellent starting point for beginners who want to get acquainted with string manipulation and array handling in Python. This problem may seem straightforward at first glance, but it also provides an opportunity to explore multiple approaches, from the naive to the more sophisticated.

Problem Statement

The problem asks us to check if two arrays of string fragments are equivalent when concatenated. Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.

For example:

word1 = ["ab", "c"]
word2 = ["a", "bc"]

The output should be True because “ab” + “c” is equal to “a” + “bc”.

Brute-Force Approach: Concatenation and Comparison

The most straightforward approach to solving this problem is to concatenate all the string fragments in both arrays and then compare the two resulting strings.

Python Code

def arrayStringsAreEqual(word1, word2):
    str1 = ''.join(word1)
    str2 = ''.join(word2)
    return str1 == str2

Time Complexity

The time complexity of this approach is O(n+m), where n is the length of word1 and m is the length of word2. This is because the join method takes O(n) time for word1 and O(m) time for word2.

Efficient Approach: Iterative Comparison

The brute-force approach involves creating two new strings, which might not be efficient for large arrays or strings. An alternative is to compare the arrays iteratively.

Python Code

def arrayStringsAreEqual(word1, word2):
    iter1, iter2 = iter(word1), iter(word2)
    frag1, frag2 = next(iter1, ''), next(iter2, '')
    i, j = 0, 0
    
    while i < len(frag1) or j < len(frag2):
        if i == len(frag1):
            frag1, i = next(iter1, ''), 0
        if j == len(frag2):
            frag2, j = next(iter2, ''), 0
        if i < len(frag1) and j < len(frag2) and frag1[i] != frag2[j]:
            return False
        if i < len(frag1): i += 1
        if j < len(frag2): j += 1
    
    return next(iter1, None) is None and next(iter2, None) is None

Time Complexity

The time complexity remains O(n+m), but we have reduced the extra space complexity to O(1) because we no longer concatenate all the strings.

Edge Cases

Case 1: Empty Arrays

Both word1 and word2 can be empty arrays. In this case, they are equivalent.

word1 = []
word2 = []

The output should be True.

Case 2: Arrays with Empty Strings

The arrays may contain empty strings, and they should be ignored in our comparison.

word1 = ["a", ""]
word2 = ["", "a"]

The output should be True.

Testing Your Solution

Before submitting your solution, you should test it with various cases, including the edge cases mentioned above.

assert arrayStringsAreEqual(["ab", "c"], ["a", "bc"]) == True
assert arrayStringsAreEqual(["a", "bc"], ["ab", "c"]) == True
assert arrayStringsAreEqual(["a", "b", "c"], ["a", "bc"]) == True
assert arrayStringsAreEqual(["abc"], ["abc"]) == True
assert arrayStringsAreEqual(["abc"], ["a", "b", "c"]) == True
assert arrayStringsAreEqual([], []) == True
assert arrayStringsAreEqual(["", ""], ["", ""]) == True
assert arrayStringsAreEqual(["a", ""], ["", "a"]) == True

Conclusion

The “Check If Two String Arrays are Equivalent” problem is an excellent way to practice your skills in Python string and array manipulation. While the problem may seem simple, implementing an efficient solution can be a bit challenging. By considering various approaches and edge cases, you not only get practice but also deepen your understanding of Python’s capabilities for handling strings and arrays.

Leave a Reply