Question

1662. Check If Two String Arrays are Equivalent

中文文档

Description

Given two string arrays word1 and word2, return_ _true_ if the two arrays represent the same string, and _false_ otherwise._

A string is represented by an array if the array elements concatenated in order forms the string.

 

Example 1:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

Example 2:

Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false

Example 3:

Input: word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true

 

Constraints:

• 1 <= word1.length, word2.length <= 103
• 1 <= word1[i].length, word2[i].length <= 103
• 1 <= sum(word1[i].length), sum(word2[i].length) <= 103
• word1[i] and word2[i] consist of lowercase letters.

Solutions

Solution 1: String Concatenation

Concatenate the strings in the two arrays into two strings, then compare whether the two strings are equal.

The time complexity is $O(m)$, and the space complexity is $O(m)$. Here, $m$ is the total length of the strings in the arrays.

class Solution:
  def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
    return ''.join(word1) == ''.join(word2)

class Solution {
  public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
    return String.join("", word1).equals(String.join("", word2));
  }
}

class Solution {
public:
  bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
    return reduce(word1.cbegin(), word1.cend()) == reduce(word2.cbegin(), word2.cend());
  }
};

func arrayStringsAreEqual(word1 []string, word2 []string) bool {
  return strings.Join(word1, "") == strings.Join(word2, "")
}

function arrayStringsAreEqual(word1: string[], word2: string[]): boolean {
  return word1.join('') === word2.join('');
}

impl Solution {
  pub fn array_strings_are_equal(word1: Vec<String>, word2: Vec<String>) -> bool {
    word1.join("") == word2.join("")
  }
}

bool arrayStringsAreEqual(char** word1, int word1Size, char** word2, int word2Size) {
  int i = 0;
  int j = 0;
  int x = 0;
  int y = 0;
  while (i < word1Size && j < word2Size) {
    if (word1[i][x++] != word2[j][y++]) {
      return 0;
    }

    if (word1[i][x] == '\0') {
      x = 0;
      i++;
    }
    if (word2[j][y] == '\0') {
      y = 0;
      j++;
    }
  }
  return i == word1Size && j == word2Size;
}

Solution 2: Direct Traversal

In Solution 1, we concatenated the strings in the two arrays into two new strings, which has additional space overhead. We can also directly traverse the two arrays and compare the characters one by one.

We use two pointers $i$ and $j$ to point to the two string arrays, and another two pointers $x$ and $y$ to point to the corresponding characters in the strings. Initially, $i = j = x = y = 0$.

Each time we compare $word1[i][x]$ and $word2[j][y]$. If they are not equal, we directly return false. Otherwise, we increment $x$ and $y$ by $1$. If $x$ or $y$ exceeds the length of the corresponding string, we increment the corresponding string pointer $i$ or $j$ by $1$, and then reset $x$ and $y$ to $0$.

If both string arrays are traversed, we return true, otherwise, we return false.

The time complexity is $O(m)$, and the space complexity is $O(1)$. Here, $m$ is the total length of the strings in the arrays.

class Solution:
  def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
    i = j = x = y = 0
    while i < len(word1) and j < len(word2):
      if word1[i][x] != word2[j][y]:
        return False
      x, y = x + 1, y + 1
      if x == len(word1[i]):
        x, i = 0, i + 1
      if y == len(word2[j]):
        y, j = 0, j + 1
    return i == len(word1) and j == len(word2)

class Solution {
  public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
    int i = 0, j = 0;
    int x = 0, y = 0;
    while (i < word1.length && j < word2.length) {
      if (word1[i].charAt(x++) != word2[j].charAt(y++)) {
        return false;
      }
      if (x == word1[i].length()) {
        x = 0;
        ++i;
      }
      if (y == word2[j].length()) {
        y = 0;
        ++j;
      }
    }
    return i == word1.length && j == word2.length;
  }
}

class Solution {
public:
  bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
    int i = 0, j = 0, x = 0, y = 0;
    while (i < word1.size() && j < word2.size()) {
      if (word1[i][x++] != word2[j][y++]) return false;
      if (x == word1[i].size()) x = 0, i++;
      if (y == word2[j].size()) y = 0, j++;
    }
    return i == word1.size() && j == word2.size();
  }
};

func arrayStringsAreEqual(word1 []string, word2 []string) bool {
  var i, j, x, y int
  for i < len(word1) && j < len(word2) {
    if word1[i][x] != word2[j][y] {
      return false
    }
    x, y = x+1, y+1
    if x == len(word1[i]) {
      x, i = 0, i+1
    }
    if y == len(word2[j]) {
      y, j = 0, j+1
    }
  }
  return i == len(word1) && j == len(word2)
}

function arrayStringsAreEqual(word1: string[], word2: string[]): boolean {
  let [i, j, x, y] = [0, 0, 0, 0];
  while (i < word1.length && j < word2.length) {
    if (word1[i][x++] !== word2[j][y++]) {
      return false;
    }
    if (x === word1[i].length) {
      x = 0;
      ++i;
    }
    if (y === word2[j].length) {
      y = 0;
      ++j;
    }
  }
  return i === word1.length && j === word2.length;
}

impl Solution {
  pub fn array_strings_are_equal(word1: Vec<String>, word2: Vec<String>) -> bool {
    let (n, m) = (word1.len(), word2.len());
    let (mut i, mut j, mut x, mut y) = (0, 0, 0, 0);
    while i < n && j < m {
      if word1[i].as_bytes()[x] != word2[j].as_bytes()[y] {
        return false;
      }
      x += 1;
      y += 1;
      if x == word1[i].len() {
        x = 0;
        i += 1;
      }
      if y == word2[j].len() {
        y = 0;
        j += 1;
      }
    }
    i == n && j == m
  }
}