Isomorphic Strings Leetcode լուծում  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon խնձոր Bloomberg facebook Google Intel LinkedIn Microsoft Պատգամախոս Անտաշ անասուն նողկալի արարած
ալգորիթմները կոդավորում HashMap հարցազրույց հարցազրույցի պատրաստում LeetCode LeetCodeSolutions String

Խնդիրի հայտարարություն  

Այս խնդրում մեզ երկու են տալիս տողերը, ա և բ. Մեր նպատակն է պարզել ՝ երկու տողերը իզոմորֆ են, թե ոչ:

Երկու տող կոչվում է իզոմորֆ, եթե և միայն այն դեպքում, երբ առաջին տողի նիշերը կարող են փոխարինվել ցանկացած նիշով (ներառյալ ինքն իրեն) դրա առաջացման բոլոր կետերում `պահպանելով նիշերի հարաբերական կարգը նույնը: Ոչ մի նիշ չի կարող նույն նիշի հետ գծել:

Օրինակ

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

Isomorphic Strings Leetcode լուծումPin

Մոտեցում  

Մենք կարող ենք օգտագործել hashmaps ՝ առաջին տողի յուրաքանչյուր նիշի փոխարինումը պահելու համար: Եթե ​​մենք հասնենք մի դիրքի, երբ առաջին նիշին փոխարինում լինի,

  • Մենք կարող ենք ստուգել, ​​թե արդյոք փոխարինումը նույնն է, ինչ մյուս տողի նիշը: Եթե ​​ոչ, տողերը չեն կարող իզոմորֆ լինել:
  • Եթե ​​առաջին նիշին փոխարինում չլինի, մենք կարող ենք ստուգել, ​​արդյոք երկրորդ նիշը օգտագործվել է որպես առաջին տողի ցանկացած այլ նիշի փոխարինում: Այս ստուգումը կարևոր է, քանի որ մենք պետք է առաջին լարի յուրաքանչյուր նիշ գծագրենք յուրահատուկ նիշի վրա: Եթե ​​գոյություն չունի որևէ նիշ, որի փոխարինումը երկրորդ նիշն է, մենք կարող ենք երկրորդ նիշը նշանակել որպես առաջին նիշի փոխարինում: Հակառակ դեպքում տողերը իզոմորֆ չեն:
Տես նաեւ,
Տեղադրեք միջանկյալ Leetcode լուծում

Ալգորիթմ

  1. Նախաձեռնել ա բնավորությունը դեպի բնավորությունը հեշմապ փոխարինումը եւ բնավորությունը դեպի բուլյան հեշմապ սովոր
  2. Կրկնել լարային յուրաքանչյուր նիշի համար s և t:
    • If փոխարինումը պարունակում s [i] որպես բանալին:
      • If փոխարինում [s [i]]! = t [i]
        • վերադարձ կեղծ
    • Ուրիշ:
      • If օգտագործված [t [i]] == ճիշտ է
        • վերադարձ կեղծ
      • սահմանել փոխարինում [s [i]] = t [i]
      • սահմանել օգտագործված [t [i]] = ճիշտ է
  3. Վերադարձիր ճշմարիտ

Isomorphic Strings 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;
}

Java ծրագիր

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 լուծույթի բարդության վերլուծություն

Timeամանակի բարդություն

Օ (Ն), Ն = տողերի երկարությունը s և t:

Տիեզերական բարդություն 

O (1), քանի որ մուտքագրման մեջ կլինի եզակի նիշերի անընդհատ քանակ:

1