İki Simli Dizinin Ekvivalent Leetcode Həlli olub olmadığını yoxlayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Facebook
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions SimBaxılıb 31

İki simli massivin ekvivalent olub olmadığını yoxlayın problem Leetcode Həll bizə ikimizi təmin edir seriallar simli. Sonra bu iki sətir massivinin ekvivalent olub olmadığını yoxlamaq istənir. Buradakı ekvivalentlik, massivlərdəki simlərin birləşdirildiyi təqdirdə istinad edilir. Sonra birləşdirildikdən sonra hər iki ip bərabər və ya eyni olacaq. Buna görə həll yolunun dərinliyinə dalmadan əvvəl əvvəlcə bir neçə nümunəyə nəzər salaq.

Nümunələr

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

İzahat: Bütün simləri birləşdirsək, hər iki sıra da "abc" edir. Beləliklə, onlar ekvivalentdir.

İki Simli Dizinin Ekvivalent Leetcode Həlli olub olmadığını yoxlayınPin

İki Simli Dizinin Ekvivalent Leetcode Həlli olub olmadığını yoxlamaq üçün yanaşma

Problem bizə iki sıra dizə verdi. İkisinin birində digərindən daha çox simli ola bilər. Ancaq birləşdirildikdə, nəticələnən hər ikisi də eyni olacaq. Əgər onlar eyni olsa, biz geriyə qayıdırıq, əksinə yalana qayıdırıq.
İndi sadə və tətbiqi asan bir həll, dizilərin hər birindəki bütün simlərin üstündən keçməkdir. Keçərkən, ipləri birləşdiririk və nəticədə iki ip yaradırıq. Beləliklə, bu birləşdirmə əməliyyatından sonra simlərin eyni olub olmadığını yoxlayacağıq. Ancaq bu əməliyyat ipləri yaratmağımızı tələb edir. Beləliklə, proses əlavə yerə ehtiyac duyur. Ancaq problemi əlavə yer istifadə etmədən həll edə bilərik.
Dörd dəyişəndən istifadə edəcəyik, hər sıra üçün ikisi. Bu dəyişənlər massivdə indekslər və sonra sətir üçün indekslər rolunu oynayacaqdır. Bu şəkildə onlardan ikisi bizə birinci massivdəki i1-ci sətrin j1-ci simvolunda olduqlarını bildirəcəkdir. Eynilə, i2-ci sətrin j2-ci xarakteri i2 və j2 ilə təmsil olunur. İndi yalnız tətbiqetmə qalır.
İstifadə edirik döngə zamanı içərisində bir neçə şərti yoxlayırıq. Hər iki serialdakı cari xarakter uyğun gəlmirsə, yalan deyirik. Əks təqdirdə, sətrin son simvolu olub olmadığını yoxlayırıq. Bu baş verərsə, simli (i) üçün istifadə edilən indeksi artırırıq və simvol indeksini (j) 0 olaraq təyin edirik. Əks halda, sadəcə j artırırıq. Nəticədə, hər iki dizi eyni vaxtda tükənərsə, doğru, başqa yanlış olaraq geri dönərik.

Kodu

İki simli massivin ekvivalent lekkod həllinə uyğun olub olmadığını yoxlamaq üçün C ++ kodu

#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

İki Simli Arrayın Ekvivalent Leetcode Həlli olub olmadığını yoxlamaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (min (N, M)), çünki kiçik simli hər bir simvoldan keçirik. Burada N və M sırasıyla birinci və ikinci sıradakı simvol sayını əks etdirir.

Kosmik Mürəkkəblik

O (1), çünki dəyişənlərin sabit sayından istifadə etdik.

 

Şərh yaz

Translate »
1