Verilmiş İki Sətrin bir-birinə izomorf olub olmadığını yoxlayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit Çiy kərpic Amazon GE Healthcare Goldman Sachs InfoEdge Kahin UHG Optum
HashMap SimBaxılıb 405

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

“Verilmiş iki simin bir-birinə izomorf olub olmadığını yoxlayın” problemində ikisini verdik strings s1 və s2. Verilən simlərin izomorf olub-olmadığını söyləyən bir proqram yazın.

Qeyd: Hər iki simldəki bütün simvollar arasında birdən birə qədər eşleme varsa, iki simin izomorf olduğu deyilir.

Giriş Formatı

Bir s1 sətri olan ilk sətir.

Başqa bir s2 sətri olan ikinci sətir.

Çıxış formatı

Verilən sətirlər izomorfikdirsə, "TRUE" yazdırın, əks halda "FASLE" yazdırın.

Məhdudiyyətlər

  • 1 <= | s1 | <= 10 ^ 5
  • 1 <= | s2 | <= 10 ^ 5
  • s1 [i] kiçik İngilis əlifbası olmalıdır
  • s2 [i] kiçik İngilis əlifbası olmalıdır

misal

aadc
mmkl
TRUE

Explanation: 'A' ilə 'm', 'd' ilə 'k' və 'c' ilə 'l' ilə eşlendiğini görə bilərik. Beləliklə, verilən simlər izomorfdur.

Verilmiş iki sətrin bir-birinə izomorf olub olmadığını yoxlamaq üçün alqoritm

1. İki s1 və s2 sətrinin uzunluqlarını tapın, əgər uzunluqlar eyni deyilsə YALAN qayıdın

2. Hər iki s1 və s2 simli eyni vaxtda keçin

    a) Əgər s1-in cari xarakteri onda ilk dəfə görünürsə, onda s2-nin cari xarakteri əvvəllər görünməməlidir.

  • Əgər s2-nin cari xarakteri görünsə, yalan işarəsini qaytarın və s2-nin cari xarakterini ziyarət olunduğu kimi qeyd edin.
  • Cari simvolların xəritələşdirilməsini saxlayın.

    b) başqa, əvvəlki s1 [i] hadisəsinin eyni simvolla uyğunlaşdırıldığını yoxlayın.

Həyata keçirilməsi

Verilmiş iki simin bir-birinə izomorf olub olmadığını yoxlamaq üçün C ++ proqramı

#include<bits/stdc++.h>
#define NO_OF_CHARS 256
using namespace std;
 
// This function returns true if s1 and s2 are ismorphic
bool isIsomorphic(string s1, string s2)
{
 
    int m = s1.length(), n = s2.length();
 
    //if lengths are not same then they are not isomorphic
    if (m != n)
      return false;
 
    // To mark visited characters in s2
    bool is_visited[NO_OF_CHARS] = {false};
 
    // To store mapping of every character from s1 to
    // that of s2. Initialize all entries of map as -1.
    int map[NO_OF_CHARS];
    memset(map, -1, sizeof(map));
 
    // P
    for (int i = 0; i < n; i++)
    {
        // If current character of s1 is seen first
        // time in it.
        if (map[s1[i]] == -1)
        {
            // If current character of s2 is already
            // seen, one to one mapping not possible
            if (is_visited[s2[i]] == true)
                return false;
 
            // Mark current character of s2 as visited
            is_visited[s2[i]] = true;
 
            // Store mapping of current characters
            map[s1[i]] = s2[i];
        }
 
        //if this is not the first appearence of char in s1
        //then check its previous appearence is mapped to the
        //respective character
        else if (map[s1[i]] != s2[i])
            return false;
    }
 
    return true;
}
 
int main()
{
   string s1,s2;
   cin>>s1>>s2;
   if(isIsomorphic(s1, s2))
   {
       cout<<"TRUE"<<endl;
   }
   else
   {
       cout<<"FALSE"<<endl;
   }
   return 0;
}

Verilən iki sətrin bir-birinə izomorf olub olmadığını yoxlamaq üçün Java proqramı

import java.util.Scanner;
class sum
{
    // This function returns true if s1 and s2 are ismorphic
    public static boolean isIsomorphic(String s1, String s2)
    {
        int m = s1.length(), n = s2.length();
        //if lengths are not same then they are not isomorphic
        if (m != n)
          return false;
        // To mark visited characters in s2
        boolean is_visited[] = new boolean[256];
        for(int i=0;i<256;i++)
        {
            is_visited[i]=false;
        }
        // To store mapping of every character from s1 to
        // that of s2. Initialize all entries of map as -1.
        int map[] = new int [256];
        for(int i=0;i<256;i++)
        {
            map[i]=-1;
        }
        // P
        for (int i = 0; i < n; i++)
        {
            // If current character of s1 is seen first
            // time in it.
            if (map[s1.charAt(i)] == -1)
            {
                // If current character of s2 is already
                // seen, one to one mapping not possible
                if (is_visited[s2.charAt(i)] == true)
                    return false;

                // Mark current character of s2 as visited
                is_visited[s2.charAt(i)] = true;

                // Store mapping of current characters
                map[s1.charAt(i)] = s2.charAt(i);
            }

            //if this is not the first appearence of char in s1
            //then check its previous appearence is mapped to the
            //respective character
            else if (map[s1.charAt(i)] != s2.charAt(i))
                return false;
        }

        return true;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        String s1 = sr.next();
        String s2 = sr.next();
        if(isIsomorphic(s1,s2)==true)
        {
            System.out.println("TRUE");
        }
        else
        {
            System.out.println("FALSE");
        }
    }
    
}
abpanban
pjhpljpl
TRUE
abpanban
pppjhljl
FALSE

İki verilmiş ipin bir-birinə izomorf olub olmadığını yoxlamaq üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) hara n verilmiş simlərin uzunluğudur. Burada sadəcə bir simli keçib başqa bir simli yoxlayırıq. Yoxlamaq üçün yalnız davamlı vaxt alırıq.

Kosmik Mürəkkəblik

O (1) çünki yalnız 256 ölçülü boşluq elan edirik. Burada böyük bir n dəyəri ilə müqayisə etsək, 256 çox azdır. Beləliklə, kosmik mürəkkəblik uyğun gəlir.

Crack Sistemi Dizayn Müsahibələri
Translate »