Проверете дали два масива от низове са еквивалентно решение на Leetcode


Ниво на трудност Лесно
Често задавани в Facebook
Низ

Проблемът Проверка дали два низови масива са еквивалентни Leetcode Solution ни предоставя две масиви на струни. Тогава ни е казано да проверим дали тези два низови масива са еквивалентни. Тук еквивалентността се отнася до факта, че ако низовете в масивите са свързани. Тогава след конкатенацията и двата низа ще бъдат равни или еднакви. Така че, преди да се потопите дълбоко в решението, нека първо разгледаме няколко примера.

Примери

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

Обяснение: И двата масива правят “abc”, ако обединим всички низове. Така че, те са еквивалентни.

Проверете дали два масива от низове са еквивалентно решение на Leetcode

Подход за проверка дали два низови масива са еквивалентно решение на Leetcode

Проблемът ни даде два масива от низове. В единия от двата може да има повече струни, отколкото в другия. Но когато се обединят, и двете получени низове ще бъдат еднакви. Ако те се окажат еднакви, ние връщаме истина, иначе ние връщаме фалшиви.
Сега просто и лесно за изпълнение решение е просто да преминете през всички низове във всеки от масивите. Докато обхождаме, ние обединяваме низовете и създаваме два резултантни низа. И така, след тази операция за конкатенация ще проверим дали низовете са еднакви. Но тази операция изисква да създадем низовете. По този начин процесът се нуждае от допълнително пространство. Но можем да разрешим проблема и на място, което е без да използваме допълнително пространство.
Ще използваме четири променливи, по две за всеки масив. Тези променливи ще действат като индекси в масива и след това индекси за низа. По този начин двама от тях ще ни кажат, че са в j1-ия символ на i1-ия низ в първия масив. По същия начин j2-ият символ на i2-ия низ е представен от i2 и j2. Сега остава само изпълнението.
Използваме цикъл while, в който проверяваме няколко условия. Ако текущият символ в двата масива не съвпада, ние връщаме false. иначе проверяваме дали сме на последния знак от низа. Ако това се случи, ние увеличаваме индекса, използван за низ (i), и задаваме индекса на знаци (j) на 0. В противен случай просто увеличаваме j. В крайна сметка, ако и двата масива са изчерпани едновременно, тогава връщаме true, else false.

код

C ++ код за проверка дали два низови масива са еквивалентно решение на Leetcode

#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), защото използвахме постоянен брой променливи.