Эки сап массивинин барабар Leetcode чечими экендигин текшериңиз


Кыйынчылык деңгээли жеңил
Көп суралган Facebook
аркан

Эки сап массивинин барабар экендигин текшерүү көйгөйү Leetcode Solution экөөбүздү камсыз кылат Arrays кылдар. Андан кийин, ушул эки сап массивинин барабар экендигин текшерүү керектигин айтышат. Бул жердеги эквиваленттүүлүк, эгер массивдердеги саптар бириктирилген болсо. Андан кийин бириктирилгенден кийин, эки сап тең же бирдей болот. Ошентип, чечимге терең сүңгүп кирүүдөн мурун, алгач бир нече мисалдарды карап көрөлү.

мисалы,

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

Түшүндүрмө: Эгерде бардык саптарды бириктирсек, эки массив тең "abc" түзөт. Демек, алар барабар.

Эки сап массивинин барабар Leetcode чечими экендигин текшериңиз

Эки саптуу массив Leetcode чечиминин эквиваленттүү экендигин текшерүү үчүн ыкма

Маселе бизге эки катар массив берди. Экөөнүн биринде экинчисине караганда көп саптар болушу мүмкүн. Бирок бириктирилгенде, экөө тең пайда болгон саптар бирдей болот. Эгер алар бирдей болуп калса, анда биз дагы чындыкты кайтарабыз, биз дагы жалган деп жооп беребиз.
Эми, жөнөкөй жана оңой ишке ашырыла турган чечим - бул ар бир массивдеги бардык саптарды кыдырып өтүү. Жүрүп жатып, кылдарды бириктирип, натыйжалуу эки сапты түзөбүз. Ошентип, бул бириктирүү операциясынан кийин, кылдар бирдей экендигин текшеребиз. Бирок бул иш бизден кылдарды жаратууну талап кылат. Ошентип, процесс кошумча орунга муктаж. Бирок кошумча орун колдонбостон, көйгөйдү чече алабыз.
Төрт өзгөрмө колдонобуз, ар бир массив үчүн экиден. Бул өзгөрмөлөр массивдеги индекстердин катарында, андан кийин сап үчүн индекстердин милдетин аткарат. Ошентип, алардын экөө биринчи массивдеги i1-саптын j1-белгисинде экендигин айтышат. Ошо сыяктуу эле, i2-саптын j2-символу i2 жана j2 менен чагылдырылган. Эми ишке ашыруу гана калды.
Биз ичинде бир нече шарттарды текшерип турган while циклин колдонобуз. Эгерде эки массивдеги учурдагы белги дал келбесе, анда "false" деп жооп беребиз. болбосо, биз саптын акыркы тамгасында экенибизди текшеребиз. Эгер ошондой боло турган болсо, анда (i) сабы үчүн колдонулган индексти көбөйтүп, (j) символ индексин 0 деп коёбуз. Болбосо, жөн гана j көбөйтүңүз. Акыр-аягы, эгерде эки массив тең түгөнүп калса, анда true, else 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

Эки сап массивинин барабар Leetcode чечиминин текшерүүсү үчүн Java коду

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), анткени биз өзгөрүлмөлөрдүн туруктуу санын колдондук.