Изоморфты тізбектер лист кодының шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon алма Bloomberg Facebook Google Intel LinkedIn Microsoft Oracle Yahoo
HashMap String

Проблемалық мәлімдеме

Бұл мәселеде бізге екі беріледі жолдар, a және b. Біздің мақсатымыз - екі жолдың изоморфты немесе жоқ екенін анықтау.

Екі жолды изоморфты деп атайды, егер тек бірінші жолдағы таңбалар кез келген символмен (оның ішінде) оның пайда болуының барлық нүктелерінде символдардың салыстырмалы ретін бірдей сақтай отырып алмастырса ғана. Бір таңбаға екі таңба салыстыра алмайды.

мысал

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

Изоморфты тізбектер лист кодының шешімі

жақындау

Біз бірінші жолдағы әрбір таңбаның орнын сақтау үшін хэшмаптарды пайдалана аламыз. Егер біз бірінші кейіпкерді алмастыратын жағдайға жетсек,

  • Ауыстырудың басқа жолдағы таңбамен бірдей екендігін тексере аламыз. Егер олай болмаса, жолдар изоморфты бола алмайды.
  • Егер бірінші таңбаға ауыстыру болмаса, біз екінші символдың бірінші жолдағы кез келген басқа таңбаның орнына қолданылғанын тексере аламыз. Бұл тексеру өте маңызды, өйткені біз бірінші жолдағы барлық таңбаларды бірегей таңбалармен салыстыруымыз керек. Егер ауыстыру екінші таңба болатын бірде-бір символ болмаса, біз екінші символды бірінші символды ауыстыру ретінде тағайындай аламыз. Әйтпесе, жолдар изоморфты емес.

Алгоритм

  1. Инициализациялау кейіпкер дейін кейіпкер хэшмап ауыстыру және кейіпкер дейін логикалық хэшмап пайдаланылған
  2. Жолдағы барлық таңбалар үшін қайталау s және t:
    • If ауыстыру құрамында бар s [i] кілт ретінде:
      • If ауыстыру [s [i]]! = t [i]
        • жалған қайтару
    • Басқа:
      • If қолданылған [t [i]] == шын
        • жалған қайтару
      • жиынтық ауыстыру [s [i]] = t [i]
      • жиынтық қолданылған [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;
}

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

Уақыттың күрделілігі

O (N), N = s және t жолдарының ұзындығы.

Ғарыштың күрделілігі 

O (1), өйткені кірісте бірегей таңбалардың тұрақты саны болады.