Рішення ізоморфних струн Leetcode  


Рівень складності Легко
Часто запитують у саман Амазонка Apple Bloomberg Facebook Google Intel LinkedIn Microsoft оракул Yahoo
алгоритми кодування HashMap інтерв'ю інтерв'юпідготовка LeetCode LeetCodeSolutions рядок

Постановка проблеми  

У цій задачі нам дано два струни, a та b. Наша мета - визначити, ізоморфні ці два рядки чи ні.

Два рядки називаються ізоморфними тоді і лише тоді, коли символи першого рядка можуть бути замінені будь-якими символами (включаючи самого себе) у всіх точках його появи, зберігаючи відносний порядок символів однаковим. Жодні два символи не можуть зіставити один і той же символ.

Приклад

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

Рішення ізоморфних струн LeetcodePin

Підхід  

Ми можемо використовувати хеш-карти, щоб зберегти заміну для кожного символу в першому рядку. Якщо ми дійдемо до позиції, коли буде замінено перший символ,

  • Ми можемо перевірити, чи заміна є такою ж, як символ в іншому рядку. Якщо ні, рядки не можуть бути ізоморфними.
  • У випадку, якщо немає заміни першого символу, ми можемо перевірити, чи використовувався другий символ як заміна будь-якого іншого символу в першому рядку. Ця перевірка важлива, оскільки нам потрібно зіставити кожен символ у першому рядку з унікальним символом. Якщо не існує жодного символу, заміною якого є другий символ, ми можемо призначити другий символ як заміну першого символу. В іншому випадку рядки не є ізоморфними.
Дивись також
Вставте інтервал рішення штрих-коду

Алгоритм

  1. Ініціалізуйте a характер до характер хеш-карта заміна і характер до boolean хеш-карта використовуваний
  2. Ітерація для кожного символу в рядку s і t:
    • If заміна містить s [i] як ключ:
      • If заміна [s [i]]! = t [i]
        • return false
    • В іншому:
      • If використовується [t [i]] == true
        • return false
      • комплект заміна [s [i]] = t [i]
      • комплект used [t [i]] = true
  3. Повернення справжнім

Реалізація рішення ізометричних рядків Leetcode

Програма С ++

#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

Аналіз складності розв'язку Ізоморфних струн Леткод

Складність часу

O (N), N = довжина рядків s і t.

Складність простору 

O (1), оскільки на вході буде постійна кількість унікальних символів.

1