ដំណោះស្រាយអ៊ីសូហ្វុលលីសលីឡេកកូដ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg Facebook ក្រុមហ៊ុន google ក្រុមហ៊ុន Intel LinkedIn ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Oracle ក្រុមហ៊ុន Yahoo
ហាស់ម៉ាប់ ខ្សែអក្សរ

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងបញ្ហានេះយើងត្រូវបានផ្តល់ឱ្យពីរ ខ្សែអក្សរ, a និងខ។ គោលដៅរបស់យើងគឺចង់ប្រាប់ថាតើខ្សែទាំងពីរមិនស្មើគ្នាឬអត់។

ខ្សែពីរត្រូវបានគេហៅថា isomorphic ប្រសិនបើនិងប្រសិនបើតួអក្សរនៅក្នុងខ្សែទីមួយអាចត្រូវបានជំនួសដោយតួអក្សរណាមួយ (រួមទាំងខ្លួនវាផ្ទាល់) នៅគ្រប់ចំណុចនៃការកើតឡើងរបស់វាខណៈពេលដែលរក្សាលំដាប់ទាក់ទងនៃតួអក្សរដូចគ្នា។ គ្មានតួអក្សរពីរអាចគូសផែនទីទៅតួអក្សរដូចគ្នា

ឧទាហរណ៍

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

ដំណោះស្រាយអ៊ីសូហ្វុលលីសលីឡេកកូដ

វិធីសាស្រ្ត

យើងអាចប្រើ hashmaps ដើម្បីរក្សាទុកការជំនួសសម្រាប់រាល់តួអក្សរទាំងអស់នៅក្នុងខ្សែទីមួយ។ ប្រសិនបើយើងឈានដល់ទីតាំងដែលមានការជំនួសតួអក្សរដំបូង។

  • យើងអាចពិនិត្យមើលថាតើការជំនួសគឺដូចគ្នានឹងតួអក្សរនៅក្នុងខ្សែអក្សរផ្សេងទៀតដែរឬទេ។ បើមិនដូច្នោះទេខ្សែពួរមិនអាចជាអ៊ីដ្រូហ្វុកទេ។
  • ក្នុងករណីដែលមិនមានការជំនួសតួអក្សរទីមួយយើងអាចពិនិត្យមើលថាតើតួអក្សរទីពីរត្រូវបានគេប្រើជាអ្នកជំនួសសម្រាប់តួអក្សរផ្សេងទៀតនៅក្នុងខ្សែអក្សរទីមួយ។ ការត្រួតពិនិត្យនេះគឺសំខាន់ណាស់ព្រោះយើងត្រូវគូសផែនទីរាល់តួអក្សរទាំងអស់ក្នុងខ្សែទីមួយទៅតួអក្សរពិសេសមួយ។ ប្រសិនបើមិនមានតួអក្សរដែលការជំនួសជាតួអក្សរទីពីរយើងអាចចាត់តាំងតួអក្សរទីពីរជាការជំនួសតួអក្សរទីមួយ។ បើមិនដូច្នោះទេខ្សែពួរមិនមែនជាអ៊ីដ្រូហ្វុកទេ។

ក្បួនដោះស្រាយ

  1. ចាប់ផ្តើមក តួអក្សរ ទៅ តួអក្សរ hashmap ជំនួស និង តួអក្សរ ទៅ ប៊ូលីន hashmap ដែលប្រើ
  2. Iterate សម្រាប់រាល់តួអក្សរនៅក្នុងខ្សែអក្សរ s និង t:
    • If ជំនួស មាន s [ខ្ញុំ] ជាកូនសោ៖
      • If ការជំនួស [s [ខ្ញុំ]]! = t [ខ្ញុំ]
        • ត្រឡប់មិនពិត
    • ផ្សេងទៀត៖
      • If បានប្រើ [t [ខ្ញុំ]] == ពិត
        • ត្រឡប់មិនពិត
      • សំណុំ ការជំនួស [s [ខ្ញុំ]] = t [ខ្ញុំ]
      • សំណុំ used [t [i]] = ពិត
  3. ត្រឡប់ពិត

ការអនុវត្តដំណោះស្រាយអ៊ីសូហ្វុលលីសឺឡេសសូល

កម្មវិធី 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

ការវិភាគស្មុគ្រស្មាញនៃដំណោះស្រាយអ៊ីសូហ្វុលលីសឡឺកូដ

ស្មុគស្មាញពេលវេលា

ឱ (ន។ ) ន = ប្រវែងនៃខ្សែអក្សរ s និង t ។

ភាពស្មុគស្មាញនៃលំហ 

ឱ (១), ដូចដែលនឹងមានចំនួនថេរនៃតួអក្សរតែមួយគត់នៅក្នុងការបញ្ចូល។