შეამოწმეთ, არის თუ არა ორი სტრიქონიანი მასივი ეკვივალენტური Leetcode ამოხსნა


Რთული ტური Easy
ხშირად ეკითხებიან Facebook
სიმებიანი

პრობლემა შეამოწმეთ, არის თუ არა ორი სტრიქონის მასივი ეკვივალენტური Leetcode ამოხსნა გვაძლევს ორს მასივები სიმების. შემდეგ გვეუბნებიან, შეამოწმეთ ექვივალენტია თუ არა ეს ორი სიმებიანი მასივი. აქ ეკვივალენტობა აღნიშნავს იმ ფაქტს, რომ თუ მასივებში სიმები გაერთიანებულია. შემდეგ შერწყმის შემდეგ, ორივე სტრიქონი ტოლი ან იგივე იქნება. სანამ ხსნარში სიღრმეში ჩავუღრმავდებით, ჯერ გადავხედოთ რამდენიმე მაგალითს.

მაგალითები

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

განმარტება: ორივე მასივი ქმნის "abc" - ს, თუ ყველა სტრიქონს გავაერთიანებთ. ასე რომ, ისინი ეკვივალენტურია.

შეამოწმეთ, არის თუ არა ორი სტრიქონიანი მასივი ეკვივალენტური Leetcode ამოხსნა

მიდგომა შეამოწმეთ, არის თუ არა ორი სტრიქონის მასივი ეკვივალენტური Leetcode ამოხსნა

პრობლემა მოგვცა სიმების ორი მასივი. ერთში შეიძლება მეტი სიმები იყოს, ვიდრე მეორეში. როდესაც გაერთიანდება, ორივე შედეგიანი სტრიქონი იგივე იქნება. თუ ისინი იგივე იქნება, ჩვენ ვბრუნდებით ჭეშმარიტად, ჩვენ ვუბრუნდებით ცრუ.
ახლა მარტივი და მარტივი განსახორციელებელი გამოსავალია თითოეული მასივის ყველა სტრიქონის გადაკვეთა. გადაკვეთისას ჩვენ ვაერთიანებთ სტრიქონებს და ვქმნით ორ შედეგობრივ სტრიქონს. ასე რომ, ამ დამაკავშირებელი ოპერაციის შემდეგ, ჩვენ შეამოწმებთ, სიმები იგივეა. მაგრამ ეს ოპერაცია მოითხოვს სტრიქონების შექმნას. ამრიგად, პროცესს დამატებითი სივრცე სჭირდება. მაგრამ ჩვენ ასევე შეგვიძლია პრობლემის მოგვარება ისეთ ადგილას, სადაც არ არის დამატებითი სივრცე.
ჩვენ გამოვიყენებთ ოთხ ცვლადს, ორი თითოეული მასივისთვის. ეს ცვლადები იმოქმედებენ მასივის ინდექსებად, შემდეგ კი სტრიქონის ინდექსებად. ამ გზით ორი მათგანი გვეტყვის, რომ ისინი არიან პირველი მასივის i1 სიმების j1-ე სიმბოლოში. ანალოგიურად, i2th სტრიქონის j2th სიმბოლო წარმოდგენილია i2 და j2. ახლა დარჩენილია მხოლოდ განხორციელება.
ჩვენ ვიყენებთ while მარყუჟს, რომლის დროსაც ვამოწმებთ რამდენიმე პირობას. თუ ორივე მასივში არსებული სიმბოლო არ ემთხვევა, ჩვენ ვუბრუნდებით false. წინააღმდეგ შემთხვევაში, ჩვენ ვამოწმებთ, ვართ თუ არა სიმების ბოლო სიმბოლო. თუ ეს მოხდა, ჩვენ მივამატებთ ინდექსს, რომელიც გამოიყენება სტრიქონისთვის (i) და დავაყენეთ სიმბოლოების ინდექსი (j) 0. წინააღმდეგ შემთხვევაში, უბრალოდ გავზარდოთ j. დაბოლოს, თუ ორივე მასივი ერთდროულად ამოწურულია, მაშინ ჩვენ ვუბრუნდებით true, სხვაგვარად 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

ჯავის კოდი იმისთვის, რომ შეამოწმოთ არის თუ არა ორი სტრიქონიანი მასივი ეკვივალენტური 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), რადგან ჩვენ გამოვიყენეთ ცვლადების მუდმივი რაოდენობა.