DEV Community

Ruairí O'Brien
Ruairí O'Brien

Posted on • Edited 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

aaravjoshi profile image

7 Powerful Python Performance Optimization Techniques for Faster Code

Aarav Joshi -

osahenru profile image

Using dj-rest-auth to integrate GitHub authentication in your Django project

Osahenru -

mdarifulhaque profile image

2461. Maximum Sum of Distinct Subarrays With Length K

MD ARIFUL HAQUE -

shafiqbd profile image

Greatest Common Divisor of Strings in Javascript

Md. Shafiqul Islam -