1662. Check If Two String Arrays are Equivalent

Hello, reader 👋🏽 ! Welcome to day 25 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 1662. Check If Two String Arrays are Equivalent.

🤔 Problem Statement

Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.
Representation of an array is the concatenation of all the elements in order to form a string.
E.g.:
- word1 = ["ab", "c"], word2 = ["a", "bc"] => true
- word1 = ["a", "cb"], word2 = ["ab", "c"] => false
- word1 = ["abc", "d", "defg"], word2 = ["abcddefg"] => true

💬 Thought Process - Build Strings

We can do exactly what the question says: build the string representations of both the arrays and check if they are equal.
The two string representations would be equal if they have the same length and the characters are the same from start to end.
This is pretty straightforward. Let's look into the code now.

👩🏽‍💻 Solution - Build Strings

Below is the code for the approach to build string representations.

class Solution {
  public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
      if(word1 == null || word1.length == 0 || 
          word2 == null || word2.length == 0) {
          return false;
      }

      int m = word1.length, n = word2.length;
      int index1 = 0, index2 = 0;

      StringBuilder s1 = new StringBuilder(""), 
        s2 = new StringBuilder("");

      while(index1 < m || index2 < n) {
          if(index1 < m) {
              s1.append(word1[index1]);
              index1++;
          }
          if(index2 < n) {
              s2.append(word2[index2]);
              index2++;
          }
      }

      return s1.length() != s2.length() ? false : areEqual(s1, s2);
  }

  private boolean areEqual(StringBuilder s1, StringBuilder s2) {
      int n = s1.length();

      for(int i = 0; i<n; i++) {
          char c1 = s1.charAt(i);
          char c2 = s2.charAt(i);

          if(c1 != c2) return false;
      }

      return true;
  }
}

Time Complexity: O(n)
  - n = max length of string representation
Space Complexity: O(n)
  - n = max length of string representation

💬 Thought Process - 4 Pointers

Instead of using separate space to build both the strings, we can use 4 pointer technique and check for equality in a single pass.
Two pointers will be used to keep track of the index of current word from both the arrays --> outer pointer.
And the other two pointers will be used to keep track of the character of the current word from the arrays --> inner pointer.
The inner pointers will be incremented until they reach the end of the current word.
Once the inner pointer reaches the final character of the word, the outer pointer is updated, and the inner pointer once again starts from 0.
This is repeated until all the words have been iterated over in both the arrays.
If both array represent the same string, it is guaranteed that at the end of the iteration the outer pointers will equal to the length of the respective arrays they point to.

👩🏽‍💻 Solution - 4 Pointers

Below is the code for 4 pointers approach.

class Solution {
  public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
      if(word1 == null || word1.length == 0 || 
      word2 == null || word2.length == 0) {
          return false;
      }

      int m = word1.length, n = word2.length;
      int index1 = 0, index2 = 0;
      int cp1 = 0, cp2 = 0; 

      while(index1 < m && index2 < n) {
          String w1 = word1[index1], w2 = word2[index2];
          int w1Len = w1.length(), w2Len = w2.length();

          char c1 = w1.charAt(cp1);
          char c2 = w2.charAt(cp2);

          if(!areCharsEqual(c1, c2)) {
              return false;
          }

          if(hasNext(cp1, w1Len)) {
              cp1++;
          }
          else {
              index1++;
              cp1 = 0;
          }

          if(hasNext(cp2, w2Len)) {
              cp2++;
          }
          else {
              index2++;
              cp2 = 0;
          }
      }

      return index1 == m && index2 == n;
  }

  private boolean areCharsEqual(char c1, char c2) {
      return c1 == c2;
  }

  private boolean hasNext(int index, int length) {
      return index < length-1;
  }
}

Time Complexity: O(n)
  - n = max length of string
Space Complexity: O(1)

You can find the code for this question in the GitHub repo here: 1662. Check If Two String Arrays are Equivalent.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!