DEV Community

loading...

Day 8 - Check If Two String Arrays are Equivalent

ruarfff profile image Ruairí O'Brien Updated on ・2 min read

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.
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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))

Enter fullscreen mode Exit fullscreen mode

Analysis

Alt Text

Alt Text

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.

Discussion (2)

pic
Editor guide
Collapse
mhmelshaaer profile image
Mouhammed Elshaaer • Edited

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;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
ruarfff profile image
Ruairí O'Brien Author

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
Enter fullscreen mode Exit fullscreen mode