Check If Two String Arrays are Equivalent Leetcode Solution

The problem Check If Two String Arrays are Equivalent Leetcode Solution provides us two arrays of strings. Then we are told to check if these two string arrays are equivalent. The equivalence here refers to the fact that if the strings in the arrays are concatenated. Then after concatenation, both the strings will be equal or the same. So before diving deep into the solution, let us first take a look at a few examples.

Examples

word1[] = {"ab", "c"}
word2[] = {"a", "bc"}

true

Explanation: Both arrays make “abc” if we concatenate all the strings. So, they are equivalent.

Approach for Check If Two String Arrays are Equivalent Leetcode Solution

The problem gave us two arrays of strings. There can be more strings in one of the two than the other. But when concatenated, both the resultant strings will be the same. If they happen to be the same we return true else we return false.
Now, a simple and easy to implement solution is to simply traverse over all the strings in each of the arrays. While traversing, we concatenate the strings and create two resultant strings. So, after this concatenation operation, we will check if the strings are the same. But this operation requires us to create the strings. Thus the process needs extra space. But we can also solve the problem in a place that is without using extra space.
We will use four variables, two for each array. These variables will act as indices in the array and then indices for the string. This way two of them will tell us they are at the j1th character of the i1th string in the first array. Similarly, the j2th character of the i2th string is represented by i2 and j2. Now all that is left is implementation.
We use a while loop inside which we check a few conditions. If the current character in both the arrays do not match we return false. else we check if we are at the last character of the string. If that happens we increment the index used for string(i) and set the character index(j) to 0. Otherwise, simply increment j. In the end, if both arrays are exhausted simultaneously, then we return true, else false.

Code

C++ code for Check If Two String Arrays are Equivalent Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

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

int main() {
  vector<string> word1 = {"ab", "c"};
  vector<string> word2 = {"a", "bc"};
  cout<<(arrayStringsAreEqual(word1, word2) ? "true" : "false");
  return 0;
}

true

Java code for Check If Two String Arrays are Equivalent Leetcode Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        int i1 = 0, j1 = 0, i2 = 0, j2 = 0;
        while(true){
            if(word1[i1].charAt(j1) != word2[i2].charAt(j2)) return false;
            if(j1 == word1[i1].length()-1){i1++; j1 = 0;}
            else j1++;
            if(j2 == word2[i2].length()-1){i2++; j2 = 0;}
            else j2++;
            if(i1 == word1.length && i2 == word2.length)
                return true;
            else if(i1 == word1.length || i2 == word2.length)
                return false;
        }
    }

  public static void main (String[] args) throws java.lang.Exception
  {
    String[] word1 = {"ab", "c"};
    String[] word2 = {"a", "bc"};
    System.out.print((arrayStringsAreEqual(word1, word2) ? "true" : "false"));
    return 0;
  }
}

true

Complexity Analysis

Time Complexity

O(min(N, M)), because we go through each character of the smaller string. Here N and M representy the number of characters in first array and second array respectively.

Space Complexity

O(1), because we used a constant number of variables.