Решение Leetcode изоморфных строк  


Сложный уровень Легко
Часто спрашивают в саман Амазонка Apple Bloomberg Facebook Google Intel LinkedIn Microsoft Oracle Yahoo
алгоритмы кодирование HashMap Интервью подготовка к собеседованию LeetCode LeetCodeSolutions строка

Постановка задачи  

В этой задаче нам даны два струны, а и б. Наша цель - определить, изоморфны эти две струны или нет.

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

Пример

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

Решение Leetcode изоморфных строкшпилька

Подход  

Мы можем использовать хэш-карты, чтобы сохранить замену для каждого символа в первой строке. Если мы достигнем позиции, где есть замена для первого символа,

  • Мы можем проверить, совпадает ли замена с символом в другой строке. В противном случае строки не могут быть изоморфными.
  • Если нет замены для первого символа, мы можем проверить, использовался ли второй символ в качестве замены для любого другого символа в первой строке. Эта проверка важна, потому что нам нужно сопоставить каждый символ в первой строке с уникальным символом. Если не существует символа, замена которого является вторым символом, мы можем назначить второй символ как замену первого символа. В противном случае струны не изоморфны.
Смотрите также
Вставить интервал решения Leetcode

Алгоритм

  1. Инициализировать персонаж в персонаж хэш-карта замена и персонаж в логический хэш-карта используемый
  2. Итерировать для каждого символа в строке s и t:
    • If замена содержит s [i] как ключ:
      • If замена [s [i]]! = t [i]
        • вернуть ложь
    • Остальное:
      • If использовано [t [i]] == true
        • вернуть ложь
      • набор замена [s [i]] = t [i]
      • набор использовано [t [i]] = true
  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;
}

Программа 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 изоморфных строк

Сложность времени

О (N), N = длина строк s и t.

Космическая сложность 

О (1), так как на входе будет постоянное количество уникальных символов.

1