algoadvance

Leetcode 1662. Check If Two String Arrays are Equivalent

Problem Statement

The problem “1662. Check If Two String Arrays are Equivalent” requires us to determine if two string arrays are equivalent. Two string arrays are considered equivalent if their concatenation results in the same string.

Clarifying Questions

1. Input Constraints:
   • Are string arrays word1 and word2 non-empty?
   • What are the maximum lengths of the string arrays and the strings within them?
   • Can the strings contain special characters or digits, or are they limited to alphabets?
2. Output:
   • Should the function return a boolean indicating if the concatenation of both arrays results in equivalent strings?

Let’s assume:

• word1 and word2 contain only lowercase English letters.
• The total length of all the strings combined in both arrays does not exceed (10^4) characters.

Code

public class Solution {
    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        
        for (String word : word1) {
            sb1.append(word);
        }
        
        for (String word : word2) {
            sb2.append(word);
        }
        
        return sb1.toString().equals(sb2.toString());
    }
}

Strategy

1. StringBuilder Usage:
   • We will use StringBuilder to concatenate all the strings in each array since StringBuilder is more efficient for string concatenations compared to using the + operator repeatedly. Using a StringBuilder helps in minimizing the number of objects created and thus reduces memory overhead.
2. Concatenate Each Array:
   • Iterate over each string in word1, concatenating it into a StringBuilder.
   • Repeat this for word2.
3. Compare the Concatenated Results:
   • Convert both StringBuilder objects to strings and compare them using the equals method.

Time Complexity

• Concatenation:
  • Let ( n ) be the total number of characters in word1.
  • Let ( m ) be the total number of characters in word2.
  • The time complexity for concatenating strings in each array using StringBuilder is ( O(n) + O(m) ).
• Comparison:
  • String comparison will take ( O(\min(n, m)) ) time.

Thus, the overall time complexity is: [ O(n + m) ]

This solution is efficient and straightforward, operating within linear time relative to the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?