Day 8 - Check If Two String Arrays are Equivalent

The Problem

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^3
• 1 <= word1[i].length, word2[i].length <= 10^3
• 1 <= sum(word1[i].length), sum(word2[i].length) <= 10^3
• word1[i] and word2[i] consist of lowercase letters.

My Tests

Link to code

import pytest
from .Day8 import Solution

s = Solution()


@pytest.mark.parametrize(
    "word1,word2,expected",
    [
        (["ab", "c"], ["a", "bc"], True),
        (["a", "cb"], ["ab", "c"], False),
        (["abc", "d", "defg"], ["abcddefg"], True),        
    ],
)
def test_array_strings_are_equal(word1, word2, expected):
    assert s.arrayStringsAreEqual(word1, word2) == expected

My Solution

from typing import List


class Solution:
    def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
        return "".join(map(str, word1)) == "".join(map(str, word2))

Analysis

My Commentary

Not much to say about this one really. It's running in O(n). Not sure how to squeeze much more out of it.

We convert each list to a single string and compare them.

Comments

[Mouhammed Elshaaer]

You can optimize for memory and a much better time complexity for best-case scenarios.

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
    int w1Index=0, i=0, w1N = word1.size(),
        w2Index=0, j=0, w2N = word2.size();

    while(w1Index < w1N && w2Index < w2N) {
        if (word1[w1Index][i] != word2[w2Index][j]) return false;

        if(word1[w1Index].length() - 1 > i) ++i;
        else {
            ++w1Index;
            i = 0;
        }

        if(word2[w2Index].length() - 1 > j) ++j;
        else {
            ++w2Index;
            j = 0;
        }
    }

    return w1Index + w2Index == w1N + w2N;
}

[Ruairí O'Brien]

That's cool. Thank you!

I did a python version of it to test it out:

def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
        w1, i, w1n = 0, 0, len(word1)
        w2, j, w2n = 0, 0, len(word2)

        while w1 < w1n and w2 < w2n:
            if word1[w1][i] != word2[w2][j]:
                return False
            if len(word1[w1]) - 1 > i:
                i += 1
            else:
                w1 += 1
                i = 0

            if len(word2[w2]) - 1 > j:
                j += 1
            else:
                w2 += 1
                j = 0
        return w1 + w2 == w1n + w2n