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


Ниво на тешкотија Лесно
Често прашувано во Facebook
алгоритми кодирање интервју интервју подготви LeetCode LeetCodeSolutions Стринг

Проблемот Проверете дали две низи се еквивалентни решенија за лет код ни овозможува двајца низи на жиците. Тогаш ни е речено да провериме дали овие две низи со низи се еквивалентни. Еквивалентноста тука се однесува на фактот дека ако жиците во низите се споени. Потоа по спојувањето, двата жица ќе бидат еднакви или исти. Затоа, пред да се нурнете длабоко во решението, прво да погледнеме неколку примери.

Примери  

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

Објаснување: Двете низи прават „abc“ ако ги споиме сите низи. Значи, тие се еквивалентни.

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

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

Проблемот ни даде две низи жици. Може да има повеќе жици во едното или другото од другото. Но, кога ќе се спојат, и двата резултантни жици ќе бидат исти. Ако се случи да бидат исти, ние ќе се вратиме вистинито, ќе се вратиме лажни.
Сега, едноставно и лесно решение за имплементација е едноставно поминување низ сите низи во секоја од низите. Додека минуваме, ние ги спојуваме жиците и создаваме две резултантни жици. Значи, по оваа операција за спојување, ќе провериме дали жиците се исти. Но, оваа операција бара од нас да ги создадеме жиците. Така, на процесот му треба дополнителен простор. Но, ние исто така можеме да го решиме проблемот во место што е без користење дополнителен простор.
Useе користиме четири варијабли, по две за секоја низа. Овие променливи ќе дејствуваат како индекси во низата, а потоа и индекси за низата. На овој начин двајца од нив ќе ни кажат дека се наоѓаат во j1-от карактер на i1-та низа во првата низа. Слично на тоа, j2-от карактер на i2-та низа е претставен со i2 и j2. Сега останува само имплементација.
Ние користиме а додека јамка внатре во која проверуваме неколку услови. Ако тековниот знак во двете низи не се совпаѓа, ние враќаме лажно. инаку проверуваме дали сме на последниот знак од низата. Ако тоа се случи, го зголемуваме индексот што се користи за низата (i) и го поставуваме индексот на знаци (j) на 0. Во спротивно, едноставно го зголемуваме j. На крајот, ако двата низа се исцрпат истовремено, тогаш враќаме точно, а друго лажно.

Видете исто така
Конверзија на постфикс во Инфикс

Код  

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

Јава код за проверка дали две низи се еквивалентни решенија за лет код

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 (мин (N, M)), затоа што поминуваме низ секој карактер од помалата низа. Тука N и M претставуваат број на знаци во првата низа, соодветно, во втората низа.

Комплексноста на просторот

О (1), затоа што користевме постојан број на променливи.

 

1