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. 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!
Problem Statement
Given two strings w1 and w2, return true if the two arrays represent the same string, and false otherwise.
Input
w1 = ["bbb", "c"]
w2 = ["bb", "bc"]
Output
True
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.
Solution
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 the 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 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.
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
C++ Code 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
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.
Conclusion
In this article, we studied how you can get into your dream software company by solving competitive problems like the above. 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 respective codes.
To sharpen your competitive skills, try this Group Anagrams Problem.