Check If Two String Arrays are Equivalent

easy string two pointers

Problem

Given two arrays of strings word1 and word2, return whether concatenating each gives the same string.

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

Outputtrue

"ab"+"c" = "abc" = "a"+"bc".

word1 (e.g. ab,c)

word2

def array_strings_are_equal(word1, word2):
    i1 = j1 = i2 = j2 = 0
    while i1 < len(word1) and i2 < len(word2):
        if word1[i1][j1] != word2[i2][j2]:
            return False
        j1 += 1
        if j1 == len(word1[i1]): i1 += 1; j1 = 0
        j2 += 1
        if j2 == len(word2[i2]): i2 += 1; j2 = 0
    return i1 == len(word1) and i2 == len(word2)

function arrayStringsAreEqual(word1, word2) {
  let i1 = 0, j1 = 0, i2 = 0, j2 = 0;
  while (i1 < word1.length && i2 < word2.length) {
    if (word1[i1][j1] !== word2[i2][j2]) return false;
    if (++j1 === word1[i1].length) { i1++; j1 = 0; }
    if (++j2 === word2[i2].length) { i2++; j2 = 0; }
  }
  return i1 === word1.length && i2 === word2.length;
}

class Solution {
    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        int i1 = 0, j1 = 0, i2 = 0, j2 = 0;
        while (i1 < word1.length && i2 < word2.length) {
            if (word1[i1].charAt(j1) != word2[i2].charAt(j2)) return false;
            if (++j1 == word1[i1].length()) { i1++; j1 = 0; }
            if (++j2 == word2[i2].length()) { i2++; j2 = 0; }
        }
        return i1 == word1.length && i2 == word2.length;
    }
}

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
    int i1 = 0, j1 = 0, i2 = 0, j2 = 0;
    while (i1 < (int)word1.size() && i2 < (int)word2.size()) {
        if (word1[i1][j1] != word2[i2][j2]) return false;
        if (++j1 == (int)word1[i1].size()) { i1++; j1 = 0; }
        if (++j2 == (int)word2[i2].size()) { i2++; j2 = 0; }
    }
    return i1 == (int)word1.size() && i2 == (int)word2.size();
}

Explanation

The easy way is to glue each array into one big string and compare them, but that copies all the characters. This solution compares the two concatenations character by character without ever building them, using only constant extra space.

We keep two pairs of indices: (i1, j1) point at a word and a character inside word1, and (i2, j2) do the same for word2. So word1[i1][j1] is the current character of the first array.

Each loop step compares those two current characters. If they differ, the strings cannot be equal, so we return false. If they match, we advance both character pointers. When a pointer reaches the end of its current word, we move to the next word and reset the character index to 0.

The loop stops when either array runs out of words. At that point the arrays are equivalent only if both finished together — i1 == len(word1) and i2 == len(word2) — which catches the case where one is a prefix of the other.

Example: word1 = ["ab","c"], word2 = ["a","bc"]. We compare a-a, b-b, c-c, all matching, and both arrays finish at the same time, so the answer is true.

Time: O(n) Space: O(1)