Хоёр мөрт массив нь эквивалент Leetcode шийдэл мөн эсэхийг шалгана уу  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Facebook-ийн
алгоритмууд кодлох ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions String

Хоёр мөрт массивтай тэнцэх эсэхийг шалгах асуудал Leetcode шийдэл нь бид хоёрыг хангаж өгдөг массивууд мөрүүдийг. Дараа нь эдгээр хоёр мөрийн массив тэнцүү эсэхийг шалгахыг бидэнд хэлэв. Энд байгаа эквивалент байдал нь хэрэв массив дахь мөрүүдийг нэгтгэвэл зохино гэсэн үг юм. Дараа нь залгасны дараа хоёулаа тэнцүү эсвэл ижил байх болно. Тиймээс шийдэлд гүн орохоосоо өмнө эхлээд хэдэн жишээг авч үзье.

жишээ нь  

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

Тайлбар: Хэрэв бид бүх мөрүүдийг холбовол хоёулаа массивыг "abc" болгоно. Тиймээс, тэдгээр нь тэнцүү юм.

Хоёр мөрт массив нь эквивалент Leetcode шийдэл мөн эсэхийг шалгана ууPin

Хоёр мөрт массив нь Leetcode-ийн шийдэлтэй тэнцэх эсэхийг шалгах арга  

Асуудал нь бидэнд хоёр цуваа мөрийг өгсөн. Хоёрын аль нэгэнд нөгөөгөөсөө илүү олон чавхдас байж болно. Гэхдээ нэгтгэхэд үр дүнгийн мөрүүд хоёулаа ижил байх болно. Хэрэв тэдгээр нь адилхан тохиолдвол бид үнэнийг буцаадаг бол бид худлаа хариулдаг.
Одоо энгийн бөгөөд хэрэгжүүлэхэд хялбар шийдэл бол массив тус бүрийн бүх мөрийг дайран өнгөрөх явдал юм. Тэмцэн явахдаа бид мөрүүдийг нэгтгэж, үр дүнгийн хоёр мөрийг үүсгэдэг. Тиймээс энэхүү залгах ажиллагааны дараа бид мөрүүд ижил эсэхийг шалгана. Гэхдээ энэ ажиллагаа нь биднээс утас үүсгэхийг шаарддаг. Тиймээс үйл явцад нэмэлт зай шаардагдана. Гэхдээ бид нэмэлт зай ашиглахгүйгээр асуудлыг шийдэж чадна.
Бид массив тус бүрт хоёр хувьсагчийг ашиглах болно. Эдгээр хувьсагчид массивын индекс, дараа нь мөрийн индексийн үүрэг гүйцэтгэнэ. Ингэснээр тэдний хоёр нь эхний массив дахь i1-р мөрийн j1-р тэмдэгтэд байгааг бидэнд хэлэх болно. Үүнтэй адил i2-р мөрийн j2-р тэмдэгт нь i2 ба j2-ээр илэрхийлэгдэнэ. Одоо хэрэгжүүлэх л үлдлээ.
Бид ашигладаг а while давталт дотор бид хэд хэдэн нөхцлийг шалгадаг. Хэрэв хоёр массивын одоогийн тэмдэгт таарахгүй байвал бид худал гэж буцаана. эс тэгвэл бид мөрийн сүүлчийн тэмдэгт байгаа эсэхийг шалгана. Хэрэв ийм зүйл тохиолдвол бид string (i) -д ашиглагддаг индексийг өсгөж, тэмдэгтийн индексийг (j) 0 болгож тохируулна. Үгүй бол j -ийг нэмэгдүүлнэ. Эцэст нь хэрэв хоёр массив хоёулаа нэгэн зэрэг дууссан бол бид үнэн, өөр худлаа гэж буцаана.

мөн үзнэ үү
Инфиксийн хөрвүүлэлтийн дараахь засвар

код  

Хоёр мөрний массив нь 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), учир нь бид тогтмол тооны хувьсагч ашигладаг байсан.

 

1