检查两个字符串数组是否等效为Leetcode解决方案


难度级别 易得奖学金
经常问 Facebook

检查两个字符串数组是否等效的问题Leetcode解决方案为我们提供了两个 数组 的字符串。 然后告诉我们检查这两个字符串数组是否等效。 这里的等价指的是如果数组中的字符串是串联的。 然后,在连接后,两个字符串将相等或相同。 因此,在深入研究解决方案之前,让我们先来看一些示例。

例子

word1[] = {"ab", "c"}
word2[] = {"a", "bc"}
true

说明:如果我们将所有字符串连接在一起,则两个数组都将为“ abc”。 因此,它们是等效的。

检查两个字符串数组是否等效为Leetcode解决方案

检查两个字符串数组是否等效的Leetcode解决方案的方法

这个问题给了我们两个字符串数组。 两者中的一个可能比另一个多。 但是,当连接时,两个结果字符串将是相同的。 如果它们恰好相同,则返回true,否则返回false。
现在,一个简单且易于实现的解决方案是遍历每个数组中的所有字符串。 在遍历时,我们将字符串连接起来并创建两个结果字符串。 因此,在执行此串联操作之后,我们将检查字符串是否相同。 但是此操作需要我们创建字符串。 因此,该过程需要额外的空间。 但是我们也可以在不占用额外空间的地方解决问题。
我们将使用四个变量,每个数组两个。 这些变量将充当数组中的索引,然后充当字符串的索引。 这样,他们两个将告诉我们它们位于第一个数组中第i1个字符串的第j1个字符处。 类似地,第i2个字符串的第j2个字符由i2和j2表示。 现在剩下的就是实现了。
我们使用一个while循环,在其中检查一些条件。 如果两个数组中的当前字符都不匹配,则返回false。 否则,我们检查是否在字符串的最后一个字符处。 如果发生这种情况,我们将增加用于string(i)的索引,并将字符index(j)设置为0。否则,只需增加j。 最后,如果两个数组同时用尽,则返回true,否则返回false。

代码

检查两个字符串数组是否等效的Leetcode解决方案的C ++代码

#include <bits/stdc++.h>
using namespace std;

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
    int i1 = 0, j1 = 0, i2 = 0, j2 = 0;
    while(true){
        if(word1[i1][j1] != word2[i2][j2]) return false;
        if(j1 == word1[i1].size()-1)i1++, j1 = 0;
        else j1++;
        if(j2 == word2[i2].size()-1)i2++, j2 = 0;
        else j2++;
        if(i1 == word1.size() && i2 == word2.size())
            return true;
        else if(i1 == word1.size() || i2 == word2.size())
            return false;
    }
}

int main() {
  vector<string> word1 = {"ab", "c"};
  vector<string> word2 = {"a", "bc"};
  cout<<(arrayStringsAreEqual(word1, word2) ? "true" : "false");
  return 0;
}
true

检查两个字符串数组是否等效的Java代码Leetcode解决方案

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        int i1 = 0, j1 = 0, i2 = 0, j2 = 0;
        while(true){
            if(word1[i1].charAt(j1) != word2[i2].charAt(j2)) return false;
            if(j1 == word1[i1].length()-1){i1++; j1 = 0;}
            else j1++;
            if(j2 == word2[i2].length()-1){i2++; j2 = 0;}
            else j2++;
            if(i1 == word1.length && i2 == word2.length)
                return true;
            else if(i1 == word1.length || i2 == word2.length)
                return false;
        }
    }

  public static void main (String[] args) throws java.lang.Exception
  {
    String[] word1 = {"ab", "c"};
    String[] word2 = {"a", "bc"};
    System.out.print((arrayStringsAreEqual(word1, word2) ? "true" : "false"));
    return 0;
  }
}
true

复杂度分析

时间复杂度

O(min(N,M)),因为我们遍历了较小字符串的每个字符。 在这里,N和M分别代表第一数组和第二数组中的字符数。

空间复杂度

O(1),因为我们使用了恒定数量的变量。