DEV Community

Ruairí O'Brien
Ruairí O'Brien

Posted on • Updated on

Day 8 - Check If Two String Arrays are Equivalent

#leetcode #python

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.

Top comments (2)

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 •

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

Read next

hetal_patel profile image

How to install and run conda on Google Colab

Hetal Patel -

coderatul profile image

Thread synchronization in python's threading module

Atul Kushwaha -

czetsuya profile image

Learn to Incorporate Rolling Hurst Values into Your DataFrame

Ed Legaspi -

ethernmyth profile image

Playing with Python in node

Ethern Myth -