නූල් අරා දෙකක් සමාන ලීට්කෝඩ් විසඳුමක් දැයි පරීක්ෂා කරන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ෆේස්බුක්
String

ගැටළුව නූල් අරා දෙකක් සමානදැයි පරීක්ෂා කරන්න ලීට්කෝඩ් විසඳුම අපට දෙකක් සපයයි අරා නූල්. එවිට මෙම නූල් අරා දෙක සමාන දැයි පරීක්ෂා කිරීමට අපට කියනු ලැබේ. මෙහි සමානතාවය යන්නෙන් අදහස් කරන්නේ අරා වල ඇති නූල් එකිනෙක ගැටී ඇති බවයි. සම්මුතියෙන් පසුව, නූල් දෙකම සමාන හෝ සමාන වේ. එබැවින් විසඳුම ගැඹුරට කිමිදීමට පෙර, අපි පළමුව උදාහරණ කිහිපයක් දෙස බලමු.

උදාහරණ

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

පැහැදිලි කිරීම: අපි සියලු නූල් එකිනෙක සම්බන්ධ කළහොත් අරා දෙකම “abc” කරයි. ඉතින්, ඒවා සමානයි.

නූල් අරා දෙකක් සමාන ලීට්කෝඩ් විසඳුමක් දැයි පරීක්ෂා කරන්න

නූල් අරා දෙකක් සමාන ලීට්කෝඩ් විසඳුමක් දැයි පරීක්ෂා කිරීම සඳහා ප්‍රවේශය

ගැටලුව අපට නූල් දෙකක් ලබා දුන්නේය. දෙකෙන් එකක් අනෙකට වඩා වැඩි නූල් තිබිය හැකිය. නමුත් සංයුක්ත වූ විට, එහි ප්‍රති ing ලයක් ලෙස ඇති නූල් දෙකම එක හා සමාන වේ. ඒවා එක හා සමාන නම් අපි සත්‍යය වෙත හැරෙමු.
දැන්, සරල හා පහසුවෙන් ක්‍රියාත්මක කළ හැකි විසඳුමක් නම්, එක් එක් අරා වල ඇති සියලුම නූල් හරහා ගමන් කිරීමයි. ගමන් කරන අතරතුර, අපි නූල් එකිනෙක ගැට ගසා එහි ප්‍රති ing ලයක් ලෙස නූල් දෙකක් නිර්මාණය කරමු. එබැවින්, මෙම සංක්ෂිප්ත මෙහෙයුමෙන් පසුව, නූල් සමාන දැයි අපි පරීක්ෂා කරමු. නමුත් මෙම මෙහෙයුමට අපට නූල් සෑදීම අවශ්‍ය වේ. මේ අනුව ක්‍රියාවලියට අමතර ඉඩක් අවශ්‍ය වේ. නමුත් අපට අමතර ඉඩක් භාවිතා නොකරන ස්ථානයක ගැටලුව විසඳා ගත හැකිය.
අපි විචල්යයන් හතරක් භාවිතා කරමු, එක් එක් අරාව සඳහා දෙකක්. මෙම විචල්‍යයන් අරාවෙහි දර්ශක ලෙස ක්‍රියා කරන අතර පසුව නූල් සඳහා දර්ශක වේ. මේ ආකාරයෙන් දෙදෙනෙක් අපට කියනු ඇත්තේ ඔවුන් පළමු අරාවෙහි i1 වන නූලෙහි j1 වන අක්ෂරයේ සිටින බවයි. ඒ හා සමානව, i2 වන නූලෙහි j2 වන අක්ෂරය i2 සහ j2 මගින් නිරූපණය කෙරේ. දැන් ඉතිරිව ඇත්තේ ක්‍රියාත්මක කිරීම පමණි.
අපි කොන්දේසි කිහිපයක් පරික්ෂා කරන ඇතුළත ලූපයක් භාවිතා කරමු. අරා දෙකේම වත්මන් අක්‍ෂරය නොගැලපේ නම් අපි අසත්‍යය ලබා දෙමු. නැතිනම් අපි නූලෙහි අන්තිම අක්‍ෂරයේ දැයි පරීක්ෂා කර බලමු. එය සිදුවුවහොත් අපි (i) නූල් සඳහා භාවිතා කරන දර්ශකය වැඩි කර අක්ෂර දර්ශකය (j) 0 ලෙස සකසමු. එසේ නොමැතිනම් j වර්ධක කරන්න. අවසානයේදී, අරා දෙකම එකවරම අවසන් වී ඇත්නම්, අපි සත්‍යය වෙත හැරෙමු, එසේ නොමැතිනම් අසත්‍යය.

කේතය

නූල් අරා දෙකක් සමාන ලීට්කෝඩ් විසඳුමක් දැයි පරීක්ෂා කිරීම සඳහා සී ++ කේතය

#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 (min (N, M)), මන්ද අපි කුඩා නූලෙහි එක් එක් අක්ෂර හරහා ගමන් කරමු. මෙහි N සහ M පිළිවෙලින් පළමු අරාවෙහි සහ දෙවන අරාවෙහි අක්ෂර ගණන නිරූපණය කරයි.

අභ්‍යවකාශ සංකීර්ණතාව

O (1), මන්ද අපි නියත විචල්‍ය සංඛ්‍යාවක් භාවිතා කළ බැවිනි.