იზომორფული სიმები Leetcode ამოხსნა


Რთული ტური Easy
ხშირად ეკითხებიან Adobe Amazon Apple Bloomberg Facebook Google Intel LinkedIn microsoft Oracle Yahoo
HashMap სიმებიანი

პრობლემის განცხადება

ამ პრობლემის დროს, ჩვენ გვეძლევა ორი სიმები, ა და ბ. ჩვენი მიზანია განვსაზღვროთ, ორი სტრიქონი იზომორფულია თუ არა.

ორ სტრიქონს უწოდებენ იზომორფულ და მხოლოდ იმ შემთხვევაში, თუ პირველი სტრიქონის სიმბოლოები შეიძლება ჩანაცვლდეს ნებისმიერი სიმბოლოთი (მათ შორის თვითონ) მისი წარმოშობის ყველა წერტილში, ხოლო სიმბოლოების ფარდობითი რიგითობა იგივეა. ორ პერსონაჟს არ შეუძლია იმავე სიმბოლოს ასახვა.

მაგალითი

s = "abb"  , t = "cdd"
true
s = "Google" , t = "123456"
false

იზომორფული სიმები Leetcode ამოხსნა

მიდგომა

ჩვენ შეგვიძლია გამოვიყენოთ ჰეშმაპები, რათა დავიცვათ ჩანაცვლება პირველი სიმების ყველა სიმბოლოსთვის. თუ მივაღწევთ პოზიციას, სადაც ადგილი აქვს პირველი პერსონაჟის ჩანაცვლებას,

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

ალგორითმი

  1. ინიციალიზაცია ა ხასიათი to ხასიათი ჰაშმაპი ჩანაცვლება და ხასიათი to ლოგიკური ჰაშმაპი გამოიყენება
  2. განმეორება სტრიქონის ყველა პერსონაჟისთვის s და t:
    • If ჩანაცვლება შეიცავს s [i] როგორც გასაღები:
      • If ჩანაცვლება [s [i]]! = t [i]
        • დაბრუნება ყალბი
    • სხვა:
      • If გამოყენებულია [t [i]] == ჭეშმარიტი
        • დაბრუნება ყალბი
      • მითითებული ჩანაცვლება [s [i]] = t [i]
      • მითითებული გამოყენებულია [t [i]] = მართალია
  3. ნამდვილი დაბრუნება

იზომორფული სიმების Leetcode ამოხსნის განხორციელება

C ++ პროგრამა

#include <bits/stdc++.h>

using namespace std;

bool isIsomorphic(string s , string t) {
    int n = s.length();

    unordered_map <char , char> replacement;
    unordered_map <char , bool> used;

    for(int i = 0 ; i < n ; i++)
    {
        if(replacement.count(s[i]))
        {
            if(replacement[s[i]] != t[i])
                return false;
        }
        else
        {
            if(used[t[i]])
                return false;
            replacement[s[i]] = t[i];
            used[t[i]] = true;
        }
    }

    return true;
}

int main() {
    string s = "abb" , t = "cdd";
    cout << (isIsomorphic(s , t) ? "true" : "false") << endl;
    return 0;
}

ჯავა პროგრამა

import java.util.*;

class isomorphic_string {
    public static void main(String args[]) {
        String s = "abb" , t = "cdd";
        System.out.println(isIsomorphic(s , t) ? "true" : "false");
    }

    public static boolean isIsomorphic(String s , String t) {
        HashMap <Character , Character> replacement = new HashMap <>();
        HashMap <Character , Boolean> used = new HashMap <>();

        for(int i = 0 ; i < s.length() ; i++) {
            if(replacement.containsKey(s.charAt(i))) {
                if(replacement.get(s.charAt(i)) != t.charAt(i))
                    return false;
            }
            else {
                if(used.containsKey(t.charAt(i)))
                    return false;
                replacement.put(s.charAt(i) , t.charAt(i));
                used.put(t.charAt(i) , true);
            }
        }

        return true;
    }
}
true

იზომორფული სტრიქონების სირთულის ანალიზი Leetcode Solution

დროის სირთულე

O (N), N = სიმების სიგრძე s და t.

სივრცის სირთულე 

O (1), რადგან შეყვანისას იქნება უნიკალური სიმბოლოების მუდმივი რაოდენობა.