Question

1662. 检查两个字符串数组是否相等

English Version

题目描述

给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同，返回_ _true_ _；否则，返回 false_ 。_

数组表示的字符串 是由数组中的所有元素 按顺序 连接形成的字符串。

 

示例 1：

输入：word1 = ["ab", "c"], word2 = ["a", "bc"]
输出：true
解释：
word1 表示的字符串为 "ab" + "c" -> "abc"
word2 表示的字符串为 "a" + "bc" -> "abc"
两个字符串相同，返回 true

示例 2：

输入：word1 = ["a", "cb"], word2 = ["ab", "c"]
输出：false

示例 3：

输入：word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
输出：true

 

提示：

• 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] 和 word2[i] 由小写字母组成

解法

方法一：字符串拼接

将两个数组中的字符串拼接成两个字符串，然后比较两个字符串是否相等。

时间复杂度 $O(m)$，空间复杂度 $O(m)$。其中 $m$ 为数组中字符串的总长度。

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;
}

方法二：直接遍历

方法一中，我们是将两个数组中的字符串拼接成两个新的字符串，有额外的空间开销。我们也可以直接遍历两个数组，逐个字符比较。

我们使用两个指针 $i$ 和 $j$ 分别指向两个字符串数组，用另外两个指针 $x$ 和 $y$ 分别指向字符串对应的字符。初始时 $i = j = x = y = 0$。

每次比较 $word1[i][x]$ 和 $word2[j][y]$，如果不相等，直接返回 false。否则，将 $x$ 和 $y$ 分别加 $1$，如果 $x$ 或 $y$ 超出了对应的字符串的长度，将对应的字符串指针 $i$ 或 $j$ 加 $1$，然后将 $x$ 和 $y$ 重置为 $0$。

如果两个字符串数组遍历完毕，返回 true，否则返回 false。

时间复杂度 $O(m)$，空间复杂度 $O(1)$。其中 $m$ 为数组中字符串的总长度。

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
  }
}