As string data structure supports various kinds of in-build methods which can enable you with an efficient string manipulation process, it is most likely to be asked during technical interviews of various product-based companies. In this article, we will study one such problem which is to check if two string arrays are equivalent or not. So, let’s get started!
Two Strings Equivalent Problem
The computer is widely used for creating, inserting, and updating word processing applications in the form of textual data. Strings are one of the most important data structures which can be used in any programming language for the same reason. This is one of the most common problems with two given strings and finding if they are equivalent or not.
Here is the problem we are going to solve "Given two strings w1 and w2, return true if the two arrays represent the same string, and false otherwise."
For example, if we have two strings: w1 = ["bbb", "c"] and w2 = ["bb", "bc"], then they are equivalent because their content creates the same string 'bbbc'.
Before jumping to understand the solution to the problem, note that you are given two arrays of string. Therefore, there are possibilities that one of the arrays contains more than one string in comparison to the other, however, when all the strings inside respective arrays are concatenated, the resultant strings should turn out to be equivalent.
How to Check Two Strings Are Equivalent?
Below are two solutions by which you can solve this problem. Let us understand them in detail:
Method 1)) By String Comparison
This is one of the basic approaches to solving this problem. All you need to do is combine all the substrings in the array into one combination of strings for both the given arrays. Remember that the order of combination should not alter while the process is running.
Later, when you get both the combined substrings, simply compare them and return true as the result if all the characters are matched, and if not, return false.
Method 2) Optimal Approach
When it comes to the brute force approach, the solution requires extra space to create the new string and check whether both arrays are the same or not. However, this issue of increasing space complexity can be solved here.
In this approach, you can make use of four variables, two for each array. These variables will work as pointers for the array and strings. For instance, two of these pointers will indicate that they are pointing to a1 character of b1 string and the other two will indicate that they are pointing to a2 character of b2 string.
Here, you can make use of the while loop to check the conditions of comparison. For example, if the pointer indicates whether the characters are matched or not. If not, shift the pointer “b” to the next character by incrementing its index. At last, if both the arrays are exhausted simultaneously, then we return true otherwise false.
Here is the Java Code for checking if two string arrays are equivalent:
import java.util.*; import java.lang.*; import java.io.*; class Main { public static boolean StringArraysAreEquivalent(String[] w1, String[] w2) { int a1 = 0, b1 = 0, a2 = 0, b2 = 0; while(true){ if(w1[a1].charAt(b1) != w2[a2].charAt(b2)) return false; if(b1 == w1[a1].length()-1){a1++; b1 = 0;} else b1++; if(b2 == w2[a2].length()-1){a2++; b2 = 0;} else b2++; if(a1 == w1.length && a2 == w2.length) return true; else if(a1 == w1.length || a2 == w2.length) return false; } } public static void main (String[] args) throws java.lang.Exception { String[] w1 = {"bbb", "c"}; String[] w2 = {"bb", "bc"}; System.out.print((StringArraysAreEquivalent(w1, w2) ? "true" : "false")); return 0; } }
Output:
True
Also, here is the C++ Program for checking if two string arrays are equivalent:
#include <bits/stdc++.h> using namespace std; bool stringArrayAreEquivalent(vector<string>& w1, vector<string>& w2) { int a1 = 0, b1 = 0, i2 = 0, j2 = 0; while(true){ if(w1[a1][b1] != w2[a2][b2]) return false; if(b1 == w1[a1].size()-1)a1++, b1 = 0; else b1++; if(j2 == w2[i2].size()-1)i2++, j2 = 0; else j2++; if(a1 == w1.size() && i2 == w2.size()) return true; else if(a1 == w1.size() || i2 == w2.size()) return false; } } int main() { vector<string> w1 = {"bb", "cb"}; vector<string> w2 = {"b", "bcb"}; cout<<(stringArrayAreEquivalent(w1, w2) ? "true" : "false"); return 0; }
Output:
True
In Python, determining if two string arrays are equal means determining whether they have the same length and contain the same entries in the same order. This may be accomplished by using a simple comparison operator that compares the two arrays element by element.
Final, here is the Python Code to implement checking if two string arrays are equivalent:
def areEqual(arr1, arr2): if len(arr1) != len(arr2): return False for i in range(len(arr1)): if arr1[i] != arr2[i]: return False return True
In this method, we start by determining if the lengths of the two input arrays, arr1, and arr2, are equal. We return False if they aren't.
If the lengths of the two arrays are equal, we loop through each element and compare them element by element. We return False if any element is not equal. We return True if we have cycled over all of the elements in the two arrays and discovered that they are equal.
Time Complexity
The time complexity to check whether two string arrays are equivalent or not using the optimal approach turns out to be O(min(n, m)) where n and m represent the number of characters present in the first array and second array respectively.
Moreover, the space complexity for this approach is O(1) as we used a constant number of variables.
In the case of Python, the method has an O(n) time complexity, where n is the length of the input arrays. Because no new data structures are used, the space complexity is O(1).
Conclusion
Strings are the most likely topic to be asked during any technical interview and therefore, we understood how you can check if two string arrays are equivalent or not using two different approaches and their programs in Java, C++, and Python To sharpen your competitive skills more, try this Group Anagrams Problem as well.
